[yoklov]

No, I don't think building a neural net for image recognition qualifies.

NP problems are essentially problems where the following two properties hold:

1. No better algorithm is known than using brute force -- generating every possible result and checking if it's a valid result.

2. Checking that the given result is valid is doable in polynomial time or better. (This is less critical to understanding, but essentially your `isValidSolution(input, solution)` function needs to take `O(n)`, `O(n^2)`, `O(n^3)`, (etc.) time or better.)

Essentially, a NP problem is a problem where you have to brute force the solution, but it's easy to know when you've found the correct solution.

If P = NP that means that there are no problems where this is true -- it would mean that any problem where it's easy to know if you've found the solution also has an algorithm for finding it more efficiently than brute force.

Your neural network example doesn't apply because training a neural network doesn't require brute forcing the solution space of the neural network weights. That would be crazy. So it's a problem in P.

[zaarn]

Re1: the problem here goes a bit deeper, classically the NP problem is a problem which requires a non-deterministic turing machine to solve. Ie a machine that can explore multiple outcomes at once, even the entire problem space to some extend.

A non-deterministic turing machine can interprete multiple instructions (write 5 to tape and go to state 2 OR write 3 to tape and go to state 19) and (depending on interpretation) use the instruction that gives the result fastest or explore all instruction branches at once.

Note that the "OR" in there is not a classical if-else, it means literally the machine can pick one. There is no memory value that tells it which is correct.

Basically, problems that are polynomial on a NDTM will likely be NP on a normal machine (with some exceptions depending on the problem).

Re2: As above, verifying is actually easy as you can then simply follow the execution branch the NDTM picked on a normal deterministic turing machine.

Atleast this above is what I learned in CS course 2nd semester.

[mortdeus]

I've read a little bit about turing machines and there is also a variation that includes what is called an "oracle" machine. Do you know anything about that?

[zaarn]

An oracle machine is usually a turing machine that can tell you things about other turing machines.

An example would be the Halting-Oracle, which can tell you if a program will halt or not without running it. (Of course, this oracle doesn't actually work since your program can have the oracle's output as input and simply do the opposite)

A NP/P Oracle might be an oracle that can tell you if a more efficient algorithm for your problem exists.

Such oracles can be setup to prove certain assumptions (or disprove) based on simply logical statements (see halting problem oracle above).

Oracle machines are also not really turing machines, it's usually assumed they can do the oracling in a single operation and they're usually a black magic box (there is no need to explain how they work, they're an abstract concept).

[Isinlor]

From "TRAINING A 3-NODE NEURAL NETWORK IS NP-COMPLETE":

We consider a 2-layer, 3-node, n-input neural network whose nodes compute linear threshold functions of their inputs. We show that it is NP-complete to decide whether there exist weights and thresholds for the three nodes of this network so that it will produce output consistent with a given set of training examples.

https://papers.nips.cc/paper/125-training-a-3-node-neural-ne...

[mortdeus]

but trying to devise a program that can predict somebody's password without using brute force is a NP problem? Since its hard to discover what the password is, but trivial to check if it lets you in the vault?

I get the reasoning why people aren't sure if P = NP.

Here is another question.

What defines time? And what about a solution?

Consider the fact that in the theory of general relativity we have the twin paradox.

What if I sent a computer on a rocket at close to the speed of light and then on earth I had the same machine running the calculation that takes a million years, and then when the other computer gets back from it's interstellar vacation, I just have the computer ask the other what it's part of the solution is.

According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.

My intuition is telling me that this is probably the wrong way to think about time complexity though.

[zaarn]

Time and solution are usually abstract concepts here.

The time a turing machine takes to solve the problem can be considered local and in absense of general relativity, it doesn't matter much.

When you talk about time in NP/P, you usually talk about the O Notation (Big O and friends) which gives you the driving factor of the time needed to solve.

Ie, O(n) = 2 + 3x + 9x^2 + 9^x is n^x complexity because this part of the equation will grow much quicker than the others. In reality of course, it can take a while for the biggest part to overtake which is why searching an array linearly in CPU cache can be faster than a hashmap.

The solution in NP/P is usually reduced to either a predicate being proven true or the answer being boolean or can be reduced to either. (ie, solving a jig-saw puzzle can be reduced to "is this jig-saw puzzle solvable" which can be proven by presenting a solution)

The problem you present is not in the scope of NP/P. You're already involving multiple computers and generally here, people still assume general relativity doesn't exist. Plus NP still holds because one computer simply accessed a blackbox function (oracle) while the other solved it in NP.

Time-complexity isn't the only complexity either, you also have space-complexity.

SC tells you how much memory you need to solve a problem. Or rather, how quickly that memory need will grow. You can trade a lot of NP problems to P problems if you have "NP" space complexity.

SC complexity won't spit out a byte-accurate estimation of memory but it can tell you that O(n) = 100 + 100*x will grow linearly in size (O = x) and O(n) = 100 + x^2 will grow exponentially in memory usage (O = x^2).

[detaro]

> According to the computer that flew away the amount of time that it takes to solve the problem can be considered ~P in a way.

No, since it can only save a constant factor of time. (Also, dragging random physics into a mathematical model based on a different view of the world isn't really helpful to understanding it. "Time" is computational steps, not seconds)

[bigleagueposter]

P = NP is trivially true on machines which compute everything instantly (using paradoxes).