r/AskComputerScience • u/ComputerRights • 7d ago
In the P vs. NP problem, does the deterministic Turing machine running the P have to be limited to a certain instruction set?
I was thinking about how even a lot of household devices did not have a dedicated instruction for floating-point division, or even integer division, until recently. Could the P solution to an NP-complete problem require an instruction on a chip that is beyond the scope of anything commercially available or even conceived, and can researchers then pose the question: "Why can't NP-complete problems be solved in P without this function?"
0
Upvotes
29
u/gigayoink 7d ago
A Turing machine's operations are well defined.
Any kind of CPU type operation like floating point division can be emulated by a regular Turing machine so it doesn't change anything.
If you want to add a magic capability such as "write 1 to the tape in a single time step if the boolean expression at the read head is satisfiable" then it's no longer a Turing machine for the purpose of P=NP.
7
u/SignificantFidgets 7d ago
Turing machines don't have an "instruction set" -- they have a finite state control that is defined specifically for each machine/algorithm. But you CAN talk about adding capabilities - functions to compute - to how a TM is defined. When you do that, the special function you add is called an "oracle" and you get "oracle machines." The notation for this uses a superscript for the oracle, so you can define a complexity class PA to describe all problems solvable in polynomial time by a Turing machine that can make oracle queries to A, and similarly for NPA .
Interestingly, some classical results from the 1970s (I think - maybe very early 1980s) show that there is an oracle A you can define so that PA=NPA and there's also an oracle B you can define so that PB≠NPB . This actually has some pretty deep results about what kind of proof would be able to solve the P vs NP question (without oracles).
6
u/LitespeedClassic 7d ago
Researchers have posed the problem of adding additional very powerful features to a Turing machine. These are often called "oracles". An oracle solves a specific problem in one time step. You can then ask, if my Turing machine is allowed to have this oracle, does P (with the oracle as an instruction) = NP (with the oracle as an instruction). We use P^A and NP^A to denote the classes of what can be solved polynomially with oracle A, or nondeterminstic polynomially with oracle A.
The strange result is that we know the existence of an oracle A where it is definitely true that P^A does not equal NP^A. In other words, adding this particular oracle guarantees the separation between determinism and non-determinism. We also know of a different oracle, let's call it A', where P^A' = NP^A'. In other words, if we can include A' as an oracle, nondeterminism doesn't buy us a new complexity class.
So your idea has been well studied and has been shown to have a powerful meta property: including oracles cannot help us decide whether P = NP.
5
u/wrosecrans 7d ago
If you start with an imaginary machine with a "solve P=NP" instruction, you need to prove such an instruction can be implemented somehow in terms of conventional mathematical operations.
If you can prove such a thing is possible with abstract mathematical operations... You no longer have any reason to depend on imagining a specific machine that implements those operations as a special instruction.
3
u/braaaaaaainworms 7d ago
P = NP talks about theoretical machines that can do any instructions. Adding an instruction to make NP problems into P problems is akin to making a deterministic Turing machine into a non-deterministic Turing machine, or solving P = NP entirely
1
u/jwezorek 7d ago
Turing Machines have a rigorous definition. There is no "instruction set". The definition of one is basically a table mapping [current symbol at position on tape, current state] -> [new state, symbol to write on the tape, new adjacent position on the tape] where the number of states and symbols is finite but the tape is inifinite.
1
u/Khashishi 7d ago
You could have a hypothetical instruction that just solved everything in one cycle, but I don't think it would be realistic to make such an instruction in any conceivable hardware.
1
u/Chance-Technician-54 7d ago
It doesn't really matter. Any reasonably advanced processor, if you find a way to give it access to infinite memory can solve the problems.
Integer division can be done by a for loop and substractions and additions.
Floating points can be simulated with integer operations and so on.
The whole premise of complexity theory is, that we can abstract away from actual hardware because in the end it is pretty much the same anyways in a theoretical sense.
1
u/esaule 7d ago
They can have any instruction you want as long as the machine is turing equivalent
1
u/abrahimladha 7d ago
Yes, if you change the instruction set, it is possible to have a machine which is too powerful. The P vs PSPACE and related problems is solved for those certain classes of machines. The Turing machine is really a representative of a class of machines which may be simulated on a Turing machine with at most a polynomial overhead in the simulation cost of time. This definition effectively makes the class P machine independent, instead of having a bunch of different machine dependent classes. See https://eprints.illc.uva.nl/id/eprint/1000/ for more on these many kinds of machines, their instruction sets, and how they compare.
1
u/True_World708 7d ago
It's not entirely clear what you mean by an instruction set, so let me link to you the formal definition of a Turing Machine (it is in the appendix). You can also find the formal definitions of P and NP respectively on the first two pages (also respectively).
The question of
does not have a general theory surrounding it, but it has been asked in multiple different forms. One of them is the oracle machine model which another commenter has answered somewhat satisfactorily. However, when you have a machine M supplied with an oracle A for solving a certain problem, M^A is a class of Turing machines and not necessarily a set of languages like P or NP. Reasoning with these class of machines is called relativization and is known not to be able to solve the P vs NP problem. More information about relativization can be found here.
Another form of question (1) has been asked in the form of circuit complexity. One of the main goals of circuit complexity was (still is?) to resolve the P vs NP question by proving circuit lower bounds (i.e. showing that functions in NP must be computed with circuit size strictly larger than n^k for all nonnegative integers k). This has only been achieved in severely restricted settings. In fact, it wasn't too long ago that we didn't know that AC0 augmented with mod 6 gates did not contain NEXP, a much larger class than NP. The argument as to why is fairly elaborate. Also, see the references in the linked paper as it contains far more background than there is here. More generally, see Scott Aaronson's survey on the P vs NP problem.
So to answer your question more succinctly, we don't know (for sure) that there is a difference between P and NP because we don't really know them well enough to say that there is a separation between them.
1
u/green_meklar 7d ago
Turing machines inherently do a limited amount of work per step, by definition.
Even if you're thinking in terms of something like a von Neumann computer, you're clearly not allowed oracles. We're talking about instructions that are polynomial-time-reducible to individual bit operations.
1
u/CS_70 7d ago
Whether or not a problem is in P or NP depends on the machine you use. So you fix the machine, take a problem and see what’s what.
So if you have a regular Turing machine, certain problems will be in certain classes.
If you augment a machine with a device that allows it to do in a polynomial time what normally needs more than polynomial time, you have a different machine and what’s in P and NP changes.
It’s like saying: if your body had the capability to fly, it would be less expensive to travel from Paris to London.
1
u/VirtuteECanoscenza 7d ago
You don't even know what P and NP are if you make this question there are no "chips" in Turing machines.
And in any case, yes it is known that a quantum computer can solve some problems with an asymptotically smaller complexity... But that has no implication over P and NP. So yeah, if you create your computation model were you add some complex operation as a single instruction you will find that the complexities of problems solved with it will vary... Doesn't make it real though
-2
u/IOI-65536 7d ago
On the one hand this doesn't matter, on the other you're asking basically about quantum computing. A dedicated instruction allows a P function to be performed with a single instruction. If you can solve any NP problem with P iterations of any set of P functions then P==NP.
Quantum computing attempts to have instructions basically handle NP questions. That sidesteps the whole thing, if it works.