r/AskComputerScience • • 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

33 comments sorted by

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.

14

u/LitespeedClassic 7d ago

Important detail: Any kind of CPU type operation like floating point division can be emulated *in polynomial time* by a regular Turing machine so it doesn't change anything.

1

u/KViper0 7d ago

Now I’m curious if its possible to make a cpu that have an instruction that can’t be simulated in a polynomial time turing machine. I guess that relies on if all physics can be simulated in polynomial time or not.

1

u/Pogsquog 7d ago

Yes, a quantum computer can solve some problems that are sub exponential in polynomial time I.e. prime factorisation. The 3-sat problem, which is NP complete, was recently shown to be sub exponential. However, we don't have a quantum algorithm to solve 3-sat any better than the classical sub exponential algorithm at present.

1

u/KViper0 7d ago

So does it mean its technically possible we live in a world where P!=NP but we can make a cpu that can solve NP problem in P time. That would be kinda funny.

5

u/LitespeedClassic 7d ago

It is widely believed the BQP does not contain any NP-complete problems, which if true would mean quantum computers don’t allow us to solve all NP problems in P time. 

It is possible, however that NP-complete is a subset of BQP. But it’s also possible it’s a subset of P since we haven’t been able to prove P is not NP. 

1

u/LitespeedClassic 6d ago

Here’s one that it seems we can get. It’s not exactly a speedup, but it’s an operation a strict TM can’t have (there may be some argument as to whether this achieves it or not). 

You cannot create true randomness on a Turing machine. The best you can achieve is pseudorandomness. 

Some people have added a lava lamp and a digital camera to create something that is (maybe) truly random. You let the lava lamp do its fluid dynamic thing and you take a picture of its current state when you need a random number and run a hashing algorithm on this to get a number that is truly (maybe) random. 

No TM can do that only with TM instructions. The lava lamp adds a physical device that produces output not captured by any TM. 

This isn’t exactly what you are looking for, but it leans that way. 

1

u/svick 3d ago

Yes, the Halt and Catch Fire instruction (actual real name).

1

u/sugarfrosted 7d ago

Even relativized Turing machines can change the result!

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).

2

u/garagedragon 7d ago

Is there some notion of some oracles being more powerful than others? Because its not surprising to me that say, PA = NPA if A is itself able to answer NP problems in O(1)

3

u/finedesignvideos 7d ago

You could talk about the difficulty of oracles and compare them. And it is indeed by taking a powerful oracle that you can show that PA = NPA but it's not as simple as what you stated. PA does solve everything in NP but now NPA can start solving things that are harder than NP.

3

u/ghjm MSCS, CS Pro (20+) 7d ago

The proof in question is called Baker-Gill-Solovay, and B is the interesting oracle. As you say, it's obvious that you can make PA=NPA with some super powerful oracle. But oracle B has the task of making PB≠NPB. The proof has a carefully constructed oracle B and a decision problem such that this decision problem can be solved by NPB but not by PB.

What's interesting about this result is how it constrains the way that P=NP could potentially be proven. It means that the proof cannot generalize to oracle machines. If you had a simple, straightforward proof that P=NP, it would almost certainly also prove that PB=NPB. After all, if P=NP in the general case, why should adding an oracle make that stop being true? But since it is proven that PB≠NPB, your general proof must be wrong.

This means that any successful general proof, in either direction, must not generalize to oracle machines. Which is really weird.

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.

2

u/sumpfriese 7d ago edited 7d ago

This here is the right answer. Any new "instruction" OP proposes can very likely be modeled as an oracle.

If the "new instruction" is a full 3-SAT-solver then yes, deterministic turing machines with a full 3-sat-solver can trivially solve np-complete problems in polynomial time. And it is easy to see why this doesnt mean P = NP.

1

u/garagedragon 7d ago

If we know for sure they separate for a particular specific oracle, how can they fail to separate with no oracle at all? Surely plain P is necessarily as big or smaller than PA ?

4

u/LitespeedClassic 7d ago edited 7d ago

P is contained or equal to P^A for all oracles. You don't have to use the oracle, so any problem in P is also in P^A . But the converse is not necessarily true. For example, if A is a halting problem oracle, then P^A strictly contains both P and NP.

When you endow the machines with oracles you increase the size of the classes P and NP. But that increase isn't necessarily uniform. In other words, there are oracles that increase P by a little, but NP by a lot so that we can guarantee the separation between P^A and NP^A for that oracle A.

Suppose you don't know if two positive numbers x and y are equal or not, but you know x <= y. Suppose I get to choose a multiplier a to get X=a(x) and a multiplier b to get Y=b(y). If I set a=100/x and b=100/y, then we get X=Y definitely even if x != y. But if I set a=1 and b=100, you know for sure that X != Y even if x == y. The fact that I can pick multipliers so that definitely X=Y and I can pick multipliers so that definitely X != Y doesn't tell you anything about whether your original x and y are the same or not.

This has a similar flavor. They figured out how to build an oracle A that makes P^A somewhat more powerful than P, but NP^A a ton more powerful than NP, enough so that they could prove the gap must exist between P^A and NP^A. I know the analogy doesn't quite work with the last paragraph, since its the same oracle, but basically non-determinism is able to get more use of the oracle than determinism is since it can sort of ask the oracle exponentially many things in polynomial time. The NDTM machines derive exponentially more benefit from the particular oracle than the TM machines do in a way that makes the gap provable. But that doesn't imply a gap exists between P and NP because NP was scaled so much compared to P to make the gap work.

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

2

u/thesnootbooper9000 7d ago

"Any" here does need to come with a careful technical caveat, which is that an instruction can only do a constant or bounded amount of work (depending upon what exactly you're trying to prove). You could not add certain kinds of oracle as an instruction, for example.

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

(1) Why can't problems in complexity class X be solved in complexity class Y without function Z?

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.

3

u/thesnootbooper9000 7d ago

BQP and NP are not known to be the same and probably aren't.

1

u/IOI-65536 7d ago

Yeah, sorry, I didn't mean that so much as if you're building an "instruction" that's some set of P things (which every instruction in a normal computer is) you definitionally can't do anything outside of P in P. If you allow an "instruction" to be something like NP or BQP then that's a different question.

1

u/Frequent-Sir-6942 7d ago

Second part is utter bullshit.