Copperside
New member
- Joined
- Dec 4, 2023
- Messages
- 1
I was watching a video explaining the P=NP problem, and I think I've proven that P=NP. Although, this seems simply like stating that all problems are computable (as far as this class of problems goes - no halting problems, and no Gödel incompleteness*), which surely we knew already?
Note: This crosses over into electronic logic conventions, primarily because SAT is stated in those terms.
The time complexity is a lot lower than [imath]T(n)=n^k[/imath] though:
More like [imath]T(n)=n+3[/imath], or [imath]T(n)=1[/imath], depending upon definitions.
The video said that Cook-Levin proved that if P=NP can be proven for one problem, it's true for all problems.
One such problem is the Boolean satisfiability problem (SAT), which Cook-Levin (separately) proved is possible to calculate a proof for (in a very messy and open-ended proof), but couldn't find the proof they proved is possible.
So the SAT problem is to prove that for any set of inputs, a logic circuit/formula can be written, using only OR, AND, and NOT operations/gates, such that the output ([imath]q[/imath]) will always be 1.
If nullary operations are allowed, then [imath]q=1[/imath] should satisfy that.
Assuming they're not:
Take the n inputs labelled [imath]k_1\cdots k_n[/imath], and OR them together.
[imath]A=k_1\lor k_2\lor \cdots\lor k_{n-1}\lor k_n[/imath]
So [imath]A[/imath] will be a signal/variable dependent upon all the inputs, which is either 0 or 1. It can vary over time.
Then OR together [imath]A[/imath] with the inverse of itself:
[imath]q=\neg A\lor A[/imath]
If A=0:
[imath]q=\neg 0\lor 0=1\lor 0=1[/imath]
If A=1:
[imath]q=\neg 1\lor 1=0\lor 1=1[/imath]
Therefore:
[imath]q=\neg A\lor A=1[/imath], for any [imath]A[/imath].
That wasn't what first occurred to me though, and it doesn't give universal computation, but this does:
Any truth table can be expressed as a LUT, so a LUT is a universal gate for any number of inputs.
A LUT can perform universal computation for combinational logic; and for sequential logic, by feeding some of its outputs back as inputs.
In a way, it's a more elegant state machine. The feedback feature can form flip-flops, so the flip-flop is unnecessary in a state machine.
To avoid very large LUTs, several LUTs and some I/O can be combined with a network of interconnects: That's an FPGA.
My question is this:
P=NP is supposed to be a hard problem: What am I missing?
A friend suggested Gödel incompleteness, but that doesn't exist in electronic logic, due to the temporal domain:
If you try to describe a logic contradiction, it produces either a pulse train (clock), or a memory cell, depending upon how it's arranged.
Similarly, the halting problem doesn't occur, because it can't be described at this level: You can get an infinite loop, but only if you specify that as the desired solution.
You can describe a processor, and put software on it which describes a non-computable/non-halting function, but the hardware underneath doesn't operate at that abstraction. More usefully, you can describe the problem in hardware without a processor (flow computing), which presumably means you can't describe non-computable problems in hardware, in the first place.
Maybe I've misunderstood the question, or the definition wasn't stated rigorously enough?
Note: This crosses over into electronic logic conventions, primarily because SAT is stated in those terms.
The time complexity is a lot lower than [imath]T(n)=n^k[/imath] though:
More like [imath]T(n)=n+3[/imath], or [imath]T(n)=1[/imath], depending upon definitions.
The video said that Cook-Levin proved that if P=NP can be proven for one problem, it's true for all problems.
One such problem is the Boolean satisfiability problem (SAT), which Cook-Levin (separately) proved is possible to calculate a proof for (in a very messy and open-ended proof), but couldn't find the proof they proved is possible.
So the SAT problem is to prove that for any set of inputs, a logic circuit/formula can be written, using only OR, AND, and NOT operations/gates, such that the output ([imath]q[/imath]) will always be 1.
If nullary operations are allowed, then [imath]q=1[/imath] should satisfy that.
Assuming they're not:
Take the n inputs labelled [imath]k_1\cdots k_n[/imath], and OR them together.
[imath]A=k_1\lor k_2\lor \cdots\lor k_{n-1}\lor k_n[/imath]
So [imath]A[/imath] will be a signal/variable dependent upon all the inputs, which is either 0 or 1. It can vary over time.
Then OR together [imath]A[/imath] with the inverse of itself:
[imath]q=\neg A\lor A[/imath]
If A=0:
[imath]q=\neg 0\lor 0=1\lor 0=1[/imath]
If A=1:
[imath]q=\neg 1\lor 1=0\lor 1=1[/imath]
Therefore:
[imath]q=\neg A\lor A=1[/imath], for any [imath]A[/imath].
That wasn't what first occurred to me though, and it doesn't give universal computation, but this does:
Any truth table can be expressed as a LUT, so a LUT is a universal gate for any number of inputs.
A LUT can perform universal computation for combinational logic; and for sequential logic, by feeding some of its outputs back as inputs.
In a way, it's a more elegant state machine. The feedback feature can form flip-flops, so the flip-flop is unnecessary in a state machine.
To avoid very large LUTs, several LUTs and some I/O can be combined with a network of interconnects: That's an FPGA.
My question is this:
P=NP is supposed to be a hard problem: What am I missing?
A friend suggested Gödel incompleteness, but that doesn't exist in electronic logic, due to the temporal domain:
If you try to describe a logic contradiction, it produces either a pulse train (clock), or a memory cell, depending upon how it's arranged.
Similarly, the halting problem doesn't occur, because it can't be described at this level: You can get an infinite loop, but only if you specify that as the desired solution.
You can describe a processor, and put software on it which describes a non-computable/non-halting function, but the hardware underneath doesn't operate at that abstraction. More usefully, you can describe the problem in hardware without a processor (flow computing), which presumably means you can't describe non-computable problems in hardware, in the first place.
Maybe I've misunderstood the question, or the definition wasn't stated rigorously enough?