Suggest a change

These fields are all optional and need only
be supplied if you would like a direct reply.

Subject
Your email address
Your real name

You must answer this!

If you don't, my spam filtering will
ensure that I never see your email.

What's 8 plus five (in digits only)?

Please make your changes here and then
Editing tips and layout rules.

File: IntroducingTimeComplexity

''' <link rel="alternate" type="application/rss+xml"
'''       href="/rss.xml" title="RSS Feed">

********> width="25%"
|>>
''' <a title="Subscribe to my feed"
'''    rel="alternate"
'''    href="https://www.solipsys.co.uk/rss.xml">
'''    <img style="border-width: 0px;"
'''         src="https://www.feedburner.com/fb/images/pub/feed-icon32x32.png"
'''         align="middle"
'''         alt="" />Subscribe!</a>
_
''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
<<|
----
My latest posts can be
found here:
  * ColinsBlog
----
Previous blog posts:
  * TheLinearFrog
  * SeventyVersusOneHundredRevisited
  * HowTheFarragoWorks
  * SeventyVersusOneHundred
  * PowersOfTwoInLexOrder
  * EmergingEExpanded
  * RageInducingSystemImplementation
  * TheBookIsNotAlwaysRight
  * EmergingE
  * ImpossibleToTranslate
  * WaitingInVain
  * NonRepeatingDecimals
  * RationalRepeats
  * WhyIsItLovely
  * CompilingCryptoConnections
  * ExploringConnectionsBetweenCryptoSystems
  * ElwynBerlekampHasLeftUs
  * RootCauseAnalysisAndThePhotocopierQuestion
  * TheUpDownTides
  * TheForeAftTide
  * TheSidewaysTide
  * WrappingUpWrappingUpTheEarth
  * TheOtherWrappingTheEarthProblem
  * WrappingTheEarth
  * TheRingOfSteel
  * RoundingUpTheRopes
  * OtherOtherOtherRopeAroundTheEarth
  * RopeAroundTheEarthRefined
  * TheOtherRopeAroundTheEarth
  * ElementaryEstimates
  * LatitudeCorrection
  * JustGiveMeTheAnswer
  * MoreMusingOnPollardRho
  * IdleThoughtsAboutPollardRho
  * WhenOptimisingCodeMeasure
  * ADogCalledMixture
  * AnotherPayPalScam
  * WhyTopPostingHasWon
  * UnexpectedInteractionOfFeatures
  * ArchimedesHatBoxTheorem
  * ConsideringASphere
  * ToLinkOrNotToLink
  * GenericAdviceForWritingAThesis
  * JustTeachMyChildTheMaths
  * NotASpectatorSport
  * LeftTruncatablePrime
  * TheDoctorAndTheLawyer
  * FourPointsTwoDistancesProof
  * MeetingRonGraham
  * NapkinRingVersusSphericalCap
  * TheFourPointsPuzzle
  * RadiusOfTheEarthPartTwo
  * GrepTimingAnomaly
  * TheRadiusOfTheEarth
  * ThisWorksToCureMyHiccoughs
  * PerhapsWeSavedOne
  * ThinkingAboutMastodon
  * DisappearingTrainsOnVirgin
  * TheIndependenceGame
  * OneOfMyFavouritePuzzles
  * ThinkingAboutRecursion
  * MemorisingTheTube
  * SpikeySpheres
  * SurprisinglyQuick
  * AnUnexpectedFraction
  * YouHaveToAdmireTheirOptimism
  * RepresentativesMatter
  * PythagorasByIncircle
  * APuzzleAboutPuzzles
  * HowNotToDoTwitter
  * Calculating52FactorialByHand
  * SmallThingsMightNotBeSoSmall
  * NotIfYouHurry
  * FactoringViaGraphThreeColouring
  * AnotherProofOfTheDoodleTheorem
  * WhenObviousIsNotObvious
  * GraphThreeColouring
  * TheDoodleTheorem
  * BeCarefulWhatYouSay
  * TheMutilatedChessboardRevisited
  * AMirrorCopied
  * TheOtherOtherRopeAroundTheEarth
  * PhotocopyAMirror
  * ThePointOfTheBanachTarskiTheorem
  * SieveOfEratosthenesInPython
  * FastPerrinTest
  * RussianPeasantMultiplication
  * FindingPerrinPseudoPrimes_Part2
  * FindingPerrinPseudoPrimes_Part1
  * TheUnwiseUpdate
  * MilesPerGallon
  * TrackingAnItemOnHackerNews
  * HackerNewsUserAges
  * PokingTheDustyCorners
  * ThereIsNoTimeForThis
  * PublicallySharingLinks
  * LearningTimesTables
  * GracefulDegradation
  * DiagrammingMathsTopics
  * OnTheRack
  * SquareRootByLongDivision
  * BeyondTheBoundary
  * FillInTheGaps
  * SoftwareChecklist
  * NASASpaceCrews
  * TheBirthdayParadox
  * TheTrapeziumConundrum
  * RevisitingTheAnt
  * TheAntAndTheRubberBand
  * IrrationalsExist
  * MultipleChoiceProbabilityPuzzle
  * RandomEratosthenes
  * WrappingUpSquareDissection
  * DissectingASquarePart2
  * DissectingACircle
  * DissectingASquare
  * AnOddityInTennis
  * DecisionTreeForTennis
  * DecisionTreesInGames
  * AMatterOfConvention
  * DoYouNourishOrTarnish
  * BinarySearchReconsidered
  * TwoEqualsFour
  * TheLostPropertyOffice
  * TheForgivingUserInterface
  * SettingUpRSS
  * WithdrawingFromHackerNews
----
Additionally, some earlier writings:
  * RandomWritings.
  * ColinsBlog2010
  * ColinsBlog2009
  * ColinsBlog2008
  * ColinsBlog2007
  * ColinsBlogBefore2007
********
!! The Initial Ideas ...

A short time ago I was chatting about and working on some puzzles
with a friend, and casually mentioned something about how the
time complexity of this particular problem behaved.  What then
transpired was that my friend didn't know anything about how the
whole "Time Complexity" thing worked, and didn't understand about
$\mathcal{P}$ versus $\mathcal{NP}$ and similar concepts.

For normal people that wouldn't perhaps be so surprising, but this
friend is an outstandingly good mathematician, so I was caught out
somewhat.  But two or three years ago I'd been writing an article,
or post, or book, or something, and never got round to "publishing"
it in any form.

So here it is, in, what I hope, will be bite-sized, accessible chunks.
I would really appreciate feedback on this.  Although I'm posting
it as a series of pages on my bloggy thing, I intend to come back
and refine them as people point out errors, or places where the
explanation could be improved.  I'd love that - doing so would, to
some extent, have the effect of "crowd sourcing" the posts/pages to
become a decent resource.

And so we begin ...

!! What is "A Problem?"

There are many connected concepts, and in discussing these ideas
with people I've found that many of them have the basic ideas, but
not the technical understanding.  And that's perfectly reasonable,
because most "popular writing" doesn't actually give the technical
definitions.  And to some extent I'll be walking a rather fine line
here as well, since I don't have the background to go into the deep
technical details, but I'll try to be interesting and informative.

I'm going to talk about *X* different problems as specific examples,
where *X* may well change.  To start with, here are the "problems"
(yes, that will become a technical term) I'll be using:

* Squaring integers ( *SQR* );

* Multiplication of integers ( *MUL* );

* Factoring integers ( *FAC* );

* Hamilton Cycle ( *HAM* );

* Graph 3-Colouring ( *G3C* );

* Satisfiability ( *SAT* ).

OK, so to start with, X=6.

Some of these may not be familiar to you, so we'll start with one
that shouldn't take too much explaining: *SQR.*

So here's the setup.  I have a set of 3x5 cards, and on one side
is an integer.  That's the side that you'll get shown, and on the
other side is the square of that integer. So I might choose a card
and hold it up to you, revealing the number "23".  Your job, the
problem you face, is then to tell me what's on the other side.

[[[>50 Soon we will talk about the process of deriving the
response to each challenge.  We do that by using an algorithm,
and "Time Complexity" is analysing how long that algorithm will
take.

That's where we're going with this - understanding that analysis.
But that's some distance away yet, we need some groundwork first.
]]]
On this occasion what's on the other side will be "529", which you
can easily determine by putting 23 into a calculator and pressing
the right keys in the right order, or, if you're practised at this
sort of thing, working it out in your head.

But the idea is that one *can* "compute" what's on the other side.

So one "instance" of the problem *SQR* is the number "23".

So here's a summary of the important terms (and don't worry, we'll
go over these again):

* An *"Instance"* is a specific Challenge/Response pair.
    * We can think of this as being on an 3x5 card, with the
      challenge on one side, and the response being what you
      need to produce.

* A *"Problem"* is a set of instances.

So the problem *SQR* is a drawer full of 3x5 cards (which we call
instances), each with a positive integer on the front and the square
of that positive integer on the back.

!! Looking forward ...

I've started with *SQR* because it's easy to describe, and it feels
fairly familiar and straight-forward, whereas some of the other
problems are unfamiliar, obviously complicated, and it will come as
no surprise that there are some tricky questions about them.

What may surprise you is that we are already on the verge of some
research level maths into unanswered questions.

----

|>>
| |>> <<<< Prev <<<< ---- TheLinearFrog <<| | : | |>> >>>> Next >>>> ---- AlgorithmsAndSizesOfInstances ... <<| |
----
********>
''' <a href="https://mathstodon.xyz/@ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/images/Mastodon_Mascot.png"
'''      width="256" height="280"
'''      alt="https://mathstodon.xyz/@ColinTheMathmo"
'''     /></a>
********
''' <a href="https://mathstodon.xyz/@ColinTheMathmo/">You can follow me on Mathstodon.</a>
_ _ _ _
[[[>
''' <a href="https://twitter.com/ColinTheMathmo">Of course, you can also<br>follow me on twitter:</a>

''' <a href="https://twitter.com/ColinTheMathmo">
''' <img src="https://www.solipsys.co.uk/new/images/TwitterButton.png"
'''      title="By: TwitterButtons.net"
'''      width="212" height="69"
'''      alt="@ColinTheMathmo"
'''     /></a>
''' <img src="/cgi-bin/CountHits.py?IntroducingTimeComplexity" alt="" />
]]]
********<

----

!! Send us a comment ...

''' <form action="https://www.solipsys.co.uk/cgi-bin/FormMail.pl" method=post>
''' <input type=hidden name="recipient"               value="colinsblogcomment@solipsys.co.uk" >
''' <input type=hidden name="subject"                 value="Blog comment : IntroducingTimeComplexity"         >
''' <input type=hidden name="redirect"                value="https://www.solipsys.co.uk/new/ThankYouForYourComment.html" >
''' <input type=hidden name="missing_fields_redirect" value="https://www.solipsys.co.uk/RequestError.html">
''' <input type=hidden name="env_report"              value="REMOTE_HOST, REMOTE_ADDR, HTTP_USER_AGENT"  >
''' <input type=hidden name="print_blank_fields"      value="1"                                          >

********> width="47%"
You can send us a message here. It doesn't get published,
it just sends us an email, and is an easy way to ask any
questions, or make any comments, without having to send a
separate email. So just fill in the boxes and then
''' <font size="+4"><INPUT TYPE="submit" VALUE="CLICK HERE TO SEND"></font>
******** width="53%"
********<

''' <table cellpadding="5">
'''   <tr>
'''     <td valign="top">Your name </td> <td valign="top">:</td>
'''     <td> <input type=text name="realname" size="48"> </td>
'''   <tr>
'''     <td valign="top">Email </td> <td valign="top">:</td>
'''     <td> <input type=text name="email" size="48"> </td>
'''     </tr>
'''   <tr>
'''     <td valign="top">Message </td> <td valign="top">:</td>
'''     <td> <TEXTAREA NAME="Message" ROWS=10 COLS=64></TEXTAREA> </td>
'''     </tr>
'''   </table>

''' <center>
'''   <font size="+4">
'''     <INPUT TYPE="submit" VALUE="CLICK HERE TO SEND">
'''     </font>
'''   </center>
''' </form>

********<