First, NP doesn't mean "non polynomial", though people can imply that since there are no known polynomial solvers for NP-complete problems. It's a shorthand for "nondeterministic polynomial", but that naming is not intuitive either. It's a class of problems that has polynomial verifiers of solutions.
Second, NP-hard means the problem is either NP-complete or not in NP at all. Which is another confusing naming, because problems not in NP are NP-hard.
As a saying goes, there are two main problems in programming - naming things and cache invalidation. And in this case the former fails badly.
But remember that P is in NP, so NP-hard implies not in P (assuming P ≠ NP).
We're given a program P of length n, let's say it's a Turing machine with binary symbols on its tape. We want to know if P halts in fewer than n steps for all inputs. Notice that only the first n bits of those inputs are relevant (since it would take n+1 steps to reach the n+1th bit, by which time we'd know it hasn't halted in fewer than n steps). Hence we can answer this in exponential time: run P(000...) for n steps to see if it halts, run P(100...) for n steps, run P(010...) for n steps, etc. There are ~2ⁿ bitstrings of length < n, so it takes O(n × 2ⁿ) steps to check all inputs.
This problem is in NP, since we can check a candidate input in polynomial time, e.g. checking `P takes at least n steps on the input 01010101` requires running P on that input for at most n steps. It's also NP-complete since we can translate other NP problems into it (see the link for details)
The reason I like this example is that it gives an intuition for how "overpowered" a polynomial solution to it would be: able to infer seemingly-arbitrary information about any program, without having to actually run them. This is similar to how an oracle for the (usual) halting problem could be used to quickly prove/disprove arbitrary mathematical statements, just by feeding it a dumb, brute-force proof searcher. (Of course, we could state the same more directly, since theorem proving is itself NP-complete: checking a proof of size n is easy, but finding one seems to require exponential time; however, that seems more abstract than the running of a program on inputs)
Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out.
I mean, with the naive explanation you are I think you are left with either of two options:
1. A philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.
2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases.
I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head.
(The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)
Something along the lines of this is what you would likely need to do. Take some problem that is NP-complete. Prove it has an exponential lower bound on time complexity. You've just proved P != NP. Proof of impossibility is sufficiently common in mathematics that one of the oldest and best-known proofs of anything, Euclid's proof of the irrationality of sqrt(2), is an example of such a proof (it is impossible to express sqrt(2) as the ratio of two integers).
The philosophical issue relates more to physical non-existence. If I claim leprechauns don't exist, likely few people will argue with me, but I can't actually examine the universe outside of my own past and future light cones, so I can't really know for sure there is no part of larger existence that contains leprechauns. Even events that violate accepted physics may become possible if we live in a false vacuum that collapses to a state with a different physics at some time in the future. Proving mathematical non-existence is an entirely different animal. Trivially, any universally quantified proposition "for all X, predicate(X)" is logically equivalent to "for no X, not predicate(X)," yet proofs of such propositions abound.
You can definitely prove negatives, and we do so all the time. There's the undecidability of the halting problem, for example: there is no algorithm that can be expressed in a Turing-complete language that can determine if a particular program will halt or not.
Another fun one is the unsolvability of the quintic. You know how there's a formula for solving a quadratic equation (https://en.wikipedia.org/wiki/Quadratic_formula)? Well, there's also one for order 3 polynomials (cubics) and order 4 polynomials (quartics). But order 5 (quntics)? There is no formula that can solve quintic equations using addition, subtraction, multiplication, division, exponents, and radicals (square roots, cube roots, etc) in the general case. The theorem actually goes even further by providing explicit examples: the equation x^5 + x^3 + 1 has a root, approximately equal to -0.83762, which cannot be expressed in terms of the operations I listed above. This is all the consequence of Galois theory.
You could also add another parameter, call it K. This will be the maximum number of colors you can use. It is still easy for the box to check if a coloring fits this criteria.
For problems in NP, there is an underlying set of boxes in P. The input to an NP problem is a set of parameters that describe a box in P. In other words, any input for an NP problem corresponds to a 'fast box'. The NP problem then asks, "is there any input this fast box will accept". Such an accepted input is called a witness, because it proves that the box created by the input to the NP problem is solvable.
In the graph coloring example, instead of having a graph, a number of colors K, and a coloring to check, you now have: a graph and a number of colors, and the question 'can we find any coloring'.
We transformed a 'check a solution' into a 'find if a solution exists'. A key element here is that someone attempting the NP problem gets to look inside the box, figure out how it works.
In your example of 'you have to guess the number I thought of', you need to hand the guesser a box that will check that number. The guesser can then look inside the box to see how it works. So a simple comparison with a fixed value allows the guesser to 'read the hardcoded value from the source code'.
Do note that the box in P has to be fully deterministic.
In an NP problem, an input describes some parameters
> I am pretty sure there is something in this problem that makes it a not legal P/NP problem
It's not in the space of P and so isn't relevant to the problem, if I'm reading your post right, as it's exponential complexity
Don't worry you're not the first one mentioning it so that's something that must be some kind of colloquialism somewhere but I was asking to understand what people may have meant.
To top it all, you proved a negative (by providing a counterexample) :o)
Claim: There is no odd number in {2, 4, 6}.
Proof: 2 is not an odd number, 4 is not an odd number, 6 is not an odd number, there are no other elements in {2, 4, 6}. Therefore, there is no odd number in {2, 4, 6}.
If there was simply an absence of proof, we would be forced to conclude that we don't know whether there's an odd number in {2, 4, 6}. That's clearly not the case.
The claim "S is a set with no odd number" is equivalent to the claim "S is a set where all numbers are even", which is something I assume you agree that we can prove.
(I even wrote that he proved it himself at the end)
precondition: Either A is true or it is false.
question: is A false?
solution:
1. assume that A is true
2. <math stuff>
3. find a contradiction
4. ==> A can not be true
5. ==> therefor A is false
I am glad to learn, that I just as dumb as the average mathematician lol.
> Proving a negation is not a proof by contradiction
did I say that it is, though?
This is different from a constructive proof. "Here we have a problem, and all algorithms so far are in O(n^3). We can demonstrate the existence of a substructure in all instances of this problem which lowers the complexity to O(n^2.978)" would be a huge constructive proof in some fields. Such a breakthrough could lead to a large number of follow-up improvements.
A non-constructive breakthrough is like "Yup, this is a barrier. No clue why though, but it's hard."
iirc that's actually how many of these proofs work.
> To me it is really hard to see a useful path forward from there.
yes, CS is hard.
there are resources online, that explain the general idea, e.g. [1]. But understand the specifics, you really do need a solid foundation in theoretical math and theoretical CS
[1] https://www.quora.com/What-is-a-proof-by-contradiction-in-co...
Deleted comment
For worst-case NP-hardness, the complex instances are also laborious, while the simple instances are not laborious.
NP: Finding the solution takes more than polynomial time, but you can verify the answer is correct in polynomial time.
NP-Hard: Finding the solution takes more than polynomial time, and it also takes more than polynomial time to verify that the solution is correct.
NP-Complete: NP-Hard, but it can be transformed into any other NP-Complete problem in polynomial time. This is special because it means if you find a solution for any NP-Complete problem, you have found a solution for all of them. Finding an NP-Complete solution always seemed rather rather optimistic to me, but computer science professors obsessed over these problems.
Caveat: It has been more than 20 years since I was quizzed on this stuff, so it might be wrong.
NP-Hard: "The problem is at least as hard as any problem in NP." Basically, if X is an NP hard problem and you are given an oracle to solve X, you can solve any problem in NP by first transforming it to an instance of X and then solving it.
NP Complete: The problem is NP Hard & in NP.
Yes. This definition is equivalent to the one about being verifiable in polynomial time, since your non-deterministic TM can just have a different branch for every possible verification "oracle".
> I think the more practical definition is "not polynomial"...lol.
Well, there are non-polynomial algorithms harder than NP. If a solution can't even be verified efficiently, for example.
- If you walk backwards from where the non-deterministic Turing machine halted, the list of taken state machine transitions is polynomial in length (naturally, as the machine stopped in polynomial time).
- Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution.
This is the essence of the equivalence between being able to solve problems in NP in polynomial time on a (hypothetical) non-deterministic Turing machine and being able to deterministically verify a solution to those problems in polynomial time.
> - Walking that polynomial length list of actually-taken edges forward through the Turing machine constitutes a polynomial time verification of the solution.
These are really great explanations that would've saved me so much trouble in graduate school. Connecting the automata itself to the term "nondeterministic turing machine" is something that is sorely missed is most CS programs I think. It's usually handwaved in automata theory in order to give you enough to head to compilers. Then you run into it again in graduate school algorithms where it is once again handwaved (because not even the professor fully understands it).
But seriously for anyone reading this, please refer to the other sibling comments.
NP: you can verify the answer is correct in polynomial time. (and no other clauses)
Anything in P is in NP
You're not wrong tho. NP problems can be verified in polynomial time.
Nondetermisitic turnig machine is like a turing machine that has multiple "next steps" instead of one at a given time, and can migically choose the correct next step.
You can think it as "taking all the possible paths at the same time (but at the end only the correct one matters)". But you can also think it as "given all the 'choices' it made, check if there is actually such a path", in other words, verifying a certification.
Nondeterministic Polynomial. Where "nondeterministic" basically means you get to try every single polynomial solution in parallel.