What is "NP-complete"? - Fortune

What is "NP-complete"?

rindolf Rashad: generalised Freecell was shown to be NP-complete
Rashad NP-complete means?
rindolf Rashad: here?
Rashad Yup.
Rashad Just came back.
rindolf Rashad: did you read about NP-completeness?
Rashad Nope.
Rashad What is it?
rindolf Rashad: see https://en.wikipedia.org/wiki/NP-completeness
Rashad Too much math.
Rashad On wikipedia.
rindolf Rashad: see http://www.shlomifish.org/humour/fortunes/show.cgi?id=memoir-from-a-Physics-lesson-in-the-9th-grade
Rashad rindolf: Sometimes formality can make things more complex than they really are.
rindolf Rashad: true
Rashad rindolf: Can you give me a simple introduction?
rindolf Rashad: well, do you know what polynomial time is?
Rashad No.
rindolf Rashad: hmmm...
Rashad I know what a polynomial is.
Rashad Is this related to the BigO notation?
rindolf Rashad: yes.
rindolf Rashad: polynomial time is O(P(N)) where P(N) is a polynomial of N
Rashad OK.
Rashad I am trying to think of an exaple..
Rashad example*
sbrg two nested loops
rindolf Rashad: so it can be O(n^2) or O(n) or O(n*log(n)) or even O(n**100)
Rashad Aha.
Rashad What is 'n'? Number of operations?
Rashad Umm.
Rashad Probably not.
rindolf Rashad: the length of the input
Rashad Yeah that makes sense.
rindolf Rashad: ok.
Rashad I remember stuff about search algorithms.
Rashad n is the number of entries in an array, for example.
sbrg yep
rindolf Rashad: now, some problems's *verification algorithm* is polynomial and these problemms are called "NP"
Rashad Verification algorithm?
rindolf Rashad: verification means you verify that the solution is correct after given one.
Rashad Aha.
sbrg Rashad: for example, if I give you a list and tell you that it's sorted, you can verify in polynomial time that it is correct
sbrg by simply checking each pair of elements
Rashad A solution in freecell is a series of moves?
rindolf Rashad: yes
Rashad sbrg: I see.
Rashad OK so NP *complete* means?
rindolf Rashad: now, some problems are NP-hard which means that each of them can be used to solve any problem in NP after a polynomial transformation.
sbrg and NP complete are problems which are both in NP and NP-hard
rindolf Rashad: yes, what sbrg said,
sbrg so, NP: a problem that, when given a solution, you can verify that it is correct in polynomial time
sbrg NP-hard: a class of problems that can be converted to each other
Rashad OK.
Rashad OK.
Rashad So NP-hard does not imply NP?
rindolf Rashad: no, not necessarily
kadoban No, problems that are harder than NP are in NP-hard too
Rashad Ahhh
Rashad Now that makes sense.
Rashad *at least NP hard*
rindolf Rashad: for instance, the Halting Problem is NP hard.
Rashad OK now everything is in place for me.
rindolf Rashad: good
kadoban It gets complicated because we don't know the actual hard relationships between many of the complexity classes, like we don't actually know if P = NP or if there are problems in NP that aren't in P. Which leads to the famous question you've likely heard of.
Rashad But I am interested by how you can map NP-hard problems from one to the other.
rindolf Rashad: there's a 1 million USD prize for proving whether P is NP or not,
Rashad kadoban: It got pretty philosophical fast :P
Rashad P = ?
rindolf Rashad: P is the class of polynomial problem,s
kadoban P, the complexity class above, which is problems you can solve in polynomial time on a deterministic turing machine.
Rashad I am a bit confused now..
kadoban NP, problems you can verify solutions to in polynomial time on a deterministic turing machine.
Rashad OK so NP is about verification, P is about solving. Correct?
rindolf Rashad: well yes, but you often want to find good solutions for NP problems
Rashad What do you mean?
kadoban Correct, though that's really just a definition used for picking which complexity class. In general we're still interested in getting the answer to problems in NP
Rashad Ah.
sbrg Rashad: P is the class of problems that can be *solved* in polynomial time. NP is the class of problems *whose solution can be verified* in polynomial time.
Rashad So the concern is: Can you find a solution to NP problems faster than you can verify the given solution?
sbrg Rashad: Assuming you mean "faster or as fast", well.. you just asked whether P = NP
Rashad I see.
sbrg if you have an answer to that question, someone will give you a million dollars
Rashad But how is that not a philosophical question, though?
Rashad Let me rephrase that.
kadoban It depends, what's a "philosophical question"?
sbrg kadoban: that is ^
sbrg lol
Rashad Wouldn't a solution imply a way to verify it?
kadoban But if you're asking if it has practical consequences, it does, potentially.
sbrg Rashad: Well, take sudoku as an example
Rashad OK!
sbrg If I give you a solved sudoku, how long would it take for you to verify it?
Rashad kadoban: What kind of consequences?
sbrg it's the same every time. you just make sure that 1 to 9 appears in all rows, columns and boxes
Rashad sbrg: OK
sbrg however, does seeing the solution tell you how you solve it?
sbrg How as in, which steps
Rashad OK that's exactly what I am asking.
kadoban Rashad: For example if P = NP, then quite a lot of cryptography isn't very well founded. That would mean there were "quick" (in one way of speaking) algorithms to solve hard problems that crypto relies on, such as discrete logarithm and integer factorization.
Rashad How do you get an answer that is not completely random that in the same process of figuring it out you are unable to replicate the same logic into how you verify it?
Rashad And we're still talking about computers here so I am not sure if Newton's apple aha moment counts...
Gamah Rashad: sometimes it's easier to assert the validity a solution (P) than it is to explain it (NP)
Gamah or... those reversed
Gamah i forget.
sbrg Rashad: well, how easy is it to verify a sudoku? it's very easy. it's the same steps every time. however, does that knowledge of the rules of the game allow you to also solve the puzzle in an equal number of moves it took you to verify it?
Rashad sbrg: The solution however is ultimately guided by the rules of verification.
Gamah sbrg: poorly formed... technically speaking it can be easier to solve some given sudoko puzzles than it is to verify they are solved
Rashad Unless it is a complete shot in the dark.
sbrg Gamah: and there are lists that are already sorted. that doesn't change the lower bound for sorting. what's your point?
sbrg Rashad: Yes, it is. so one would think that it would be possible
sbrg and as Gamah pointed out, some sudokus are very easy to solve, while others are much harder
Gamah Rashad: no p
Gamah :P
sbrg the question is whether you can give an algorithm that guarantees that you can solve every sudoku within some time limit(in terms of the size of the input) that performs no more steps than you would verifying a sudoku
Gamah sbrg: i'm saying you can't apply the act of solving and the act of verifying a "solved" sudoko to p=np because in the space of sudoku, either task could be on either side of the equation
Gamah define "steps"
Gamah because it always takes less steps to solve than verify... from some perspective
Rashad rindolf: So solitaire is O(n)?
sbrg Gamah: you don't seem to understand complexity theory. we're talking about sudokus in general. I can verify *any* sudoku in some bounded polynomial time
Rashad Ah sorry, I meant verifying a solitaire solution is O(n)*.
Gamah you can also solve any sudoku
sbrg the question is whether I can somehow use the rules of verification to help me create a solution in at most as much time as it would take me to verify it. i.e. P vs NP
workmad3 iirc, np-complete problems are ones where verifying a solution is polynomial time, but calculating a solution is non-polynomial
rindolf Rashad: there are many variants of card solitaire
Gamah sbrg: but the number of sudoku permetations and soultions is not unbound...
rindolf Rashad: generalised Freecell is NP-complete
rindolf Rashad: which assumes you have n ranks of cards insetad of 13 (ace-to-king)
sbrg Gamah: for a 9x9 sudoku, no, obviously not. but we are talking about sudoku in general
Gamah hmm.
sbrg Rashad: at any rate, the point is that we just don't know whether we can use the information that lets us verify solutions in polynomial time to also construct solutions in polynomial time
Gamah i feel like sudoku is still a search problem (IE: rainbow table)
Gamah and not really applicable
workmad3 Gamah: and how long would it take you to compute that rainbow table?
sbrg by your logic, I can solve any problem that way.
sbrg i can just create a database of all sorted lists.
Gamah sure...
sbrg .. just like i can create a database of all sudokus. if we fix n, then yes, it is bounded and you can just solve it in constant time.
kadoban sbrg: Well, not really, you still have lookup time.
kadoban Oh, for fixed n I guess that doesn't matter.
sbrg constant time where a unit is defined to be the lookup time
sbrg there you go!
Gamah workmad3: that would depend on how well i could optimize the verification algo
sbrg it's all about context
workmad3 sbrg: well, you can solve it in constant time, assuming the existence of an oracle :)
Gamah the $1m question just says "a computer" and "in polynomial time"
Gamah it doesn't say i can't spend years precomputing the search space
Gamah :)
sbrg i don't think you understand what P vs NP means
workmad3 Gamah: assuming the existence of an oracle is generally not classed as a solution to P vs NP
Gamah i thought the smiley implied i was being pedantic
workmad3 Gamah: otherwise it would have been solved years ago :P
Gamah workmad3: well i was just going to use oracle DB
Gamah :)
Channel ##programming
Network Freenode