| 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 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' *verification algorithm* is polynomial and these problems 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 problems |
| 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 sudoku 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" sudoku 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 permutations and solutions is not unbound... |
| rindolf | Rashad: generalised Freecell is NP-complete |
| rindolf | Rashad: which assumes you have n ranks of cards instead 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 | :) |