P versus NP solved!!!

[Frank Vega Delgado]

P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.

I show a solution to that problem as follows:

Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.

You could read the details in the pdf attachment below

onpversusnp.pdf

Edited April 26, 2017 by Frank Vega Delgado

[DrKrettin]

P versus NP is considered one of the great open problems of science.

 

I would personally limit that to computer science. Have you claimed your million dollar prize yet?

[Raider5678]

P versus NP is considered one of the great open problems of science. This consists in knowing the answer of the following question: Is P equal to NP? This incognita was first mentioned in a letter written by John Nash to the National Security Agency in 1955. Since that date, all efforts to find a proof for this huge problem have failed.

I show a solution to that problem as follows:

Given a number x and a set S of n positive integers, MINIMUM is the problem of deciding whether x is the minimum of S. We can easily obtain an upper bound of n comparisons: find the minimum in the set and check whether the result is equal to x. Is this the best we can do? Yes, since we can obtain a lower bound of (n - 1) comparisons for the problem of determining the minimum and another obligatory comparison for checking whether that minimum is equal to x. A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer i if and only if i is in S. Given a positive integer x and a Boolean circuit C, we define SUCCINCT-MINIMUM as the problem of deciding whether x is the minimum bit integer which accepts C as input. For certain kind of SUCCINCT-MINIMUM instances, the input (x, C) is exponentially more succinct than the cardinality of the set S that represents C. Since we prove that SUCCINCT-MINIMUM is at least as hard as MINIMUM in order to the cardinality of S, then we could not decide every instance of SUCCINCT-MINIMUM in polynomial time. If some instance (x, C) is not in SUCCINCT-MINIMUM, then it would exist a positive integer y such that y < x and C accepts the bit integer y. Since we can evaluate whether C accepts the bit integer y in polynomial time and we have that y is polynomially bounded by x, then we can confirm SUCCINCT-MINIMUM is in coNP. If any single coNP problem cannot be solved in polynomial time, then P is not equal to coNP. Certainly, P = NP implies P = coNP because P is closed under complement, and therefore, we can conclude P is not equal to NP.

 

You could read the details in the pdf attachment below

For once, a theory with actual mathematical proof, and not gibberish. Congratulations my good sir!

 

And at any given moment there are about 150+ people looking at this site.

Go claim your million dollars right now.

Edited April 26, 2017 by Raider5678

[Frank Vega Delgado]

DrKrettin and Raider5678, thanks for your comments!!! Raider5678, if you have any doubt about the paper do not hesitate to ask me!!! DrKettin, I think to claim the million dollar prize, the paper need to be published in a journal and be accepted by the scientific community within two years.

[fiveworlds]

Proof: Since the empty set cannot be represented by a Boolean circuit C

 

 

 

Assume set with numbers given by 3 32 bit integers.

 

1,2,3,4 -> etc

 

Then we add the cardinality of the given set. We place each number into registers and increment a number stored in d flip flops representing the cardinality each time.

 

Then read the numbers from the registers decrementing the number each time.

 

Now we have a boolean circuit capable of representing the null set by checking the value stored in the flip flops.

 

Eg.

 

Edited April 26, 2017 by fiveworlds

[Frank Vega Delgado]

I think you cut the sentence by mistake, because the whole sentence in the paper says "Proof: Since the empty set cannot be represented by a Boolean circuit C such that there is some truth assignment T, appropriate to C, where T( C ) = true, then ...". Of course, the empty set can actually be represented by a Boolean circuit. However, it cannot be represented by a Boolean circuit which accepts at least some input if we use the definition which appears in the paper and that is exactly the other fragment of the sentence that you missed (the fragment after ".. such that..."). I will share the definition so you could understand...

 

Definition: A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer j if and only if j is in S.

 

fivewords, thank you very much for your comment...

Edited April 26, 2017 by Frank Vega Delgado

[fiveworlds]

it cannot be represented by a Boolean circuit which accepts at least some input if we use the definition which appears in the paper​.

 

Definition: A representation of a set S with n positive integers is a Boolean circuit C, such that C accepts the binary representation of a bit integer j if and only if j is in S.

 

 

The above circuit can accept the binary representation of a bit integer. If there is no number in the register then the value stored in memory by the adder will be all zeros. You can then use multiple of same and nand gates to do exactly what you say can't be done.

[Strange]

 

 

The above circuit can accept the binary representation of a bit integer. If there is no number in the register then the value stored in memory by the adder will be all zeros.

 

 

The circuit can only represent positive integers, and therefore cannot store zero to represent the empty set. (If I have understood the definition correctly).

 

Alternatively, zero is a positive (non-negative) integer. The circuit cannot represent the absence of an integer.

[Frank Vega Delgado]

Stranger, when I wrote the paper I thought zero as a positive (non-negative) integer. Indeed, I did not mention in the paper that the zero represents the empty set. The definition of zero as a positive (non-negative) integer really depends on context, so in our case we could take it as a valid argument without problem. At the same time, I did not discuss in the paper how I would represent the empty set. Indeed, I could formally represent it as a symbol which is not in the binary alphabet (just to put you an example) and later we could encoded as a specific binary string if we want...

 

Stranger, thank you so much for your comment...

 

fivewords, it follows from the self definition that a set S with n positive integers is represented by a Boolean circuit C, if and only if when a bit integer j is not in S, then C will not accept j (as result of using the Boolean logic over the definition). Hence, the empty set must be represented necessarily by the Boolean circuits which do not accept any input. Certainly, if some circuit C accepts some binary input x, then C will represent some set S which contains at least the bit integer x as element.

 

fivewords, thank you very much for your comment...

Edited April 26, 2017 by Frank Vega Delgado

[John Cuthber]

Am I the only one who read the title and thought of this?
https://wiki.lspace.org/mediawiki/Multiple_exclamation_marks

Obviously, if the OP turns up with the million dollars I'm going to look foolish.

But, if that happens I can reasonably claim that my on-line ID was stolen by someone who solved the p vs np issue.

[DrKrettin]

Am I the only one who read the title and thought of this?

https://wiki.lspace.org/mediawiki/Multiple_exclamation_marks

 

Obviously, if the OP turns up with the million dollars I'm going to look foolish.

But, if that happens I can reasonably claim that my on-line ID was stolen by someone who solved the p vs np issue.

 

That was my first thought. I'll join you in looking foolish.

[Velocity_Boy]

Well, I personally have nowhere near the adequate computer science smarts to discern as to whether your proposed solution is a viable one. Nor, to be perfectly honest, do I even understand most of your offered solution. But I wish you the best with it.

 

So this thread reminded me of how little I understood of the p..np problem. Do I took the liberty of finding a nice easy accessible article to explain it for all those interested, as I'm pretty sure I'm not the only one here who is a little fuzzy on the details of this problem.

 

Enjoy!

 

 

https://www.quora.com/What-is-an-explanation-of-P-versus-NP-problems-and-other-related-terms-in-laymans-terms

[ecoli]

 

I would personally limit that to computer science. Have you claimed your million dollar prize yet?

Forget a million dollar prize... start breaking financial system encryption and claim trillions.

[Frank Vega Delgado]

You can follow the paper in the following link:

 

https://hal.archives-ouvertes.fr/hal-01509423

[fiveworlds]

fivewords, it follows from the self definition that a set S with n positive integers is represented by a Boolean circuit C, if and only if when a bit integer j is not in S, then C will not accept j (as result of using the Boolean logic over the definition). Hence, the empty set must be represented necessarily by the Boolean circuits which do not accept any input. Certainly, if some circuit C accepts some binary input x, then C will represent some set S which contains at least the bit integer x as element.

 

Okay, well if you get that then could you not load the registers using a non-halting universal deterministic turing machine?

• P = Problems where a deterministic turing machine given input Σ does not halt
• M = (Q,Σ,Γ,δ,q0,B,F)
• Q is the finite set of states of the finite control.
• Σ is the finite set of input symbols.
• Γ is the finite set of tape symbols; Σ ⊂ Γ.
• δ : Q × Γ → Q × Γ × {L,R} is the transition function
• q0 ∈ Q is the start state.
• B ∈ Γ is the blank symbol; B 6∈ Σ.
• F ⊆ Q is the set of final or accepting states.
• M is the memory start symbol
• < is the tape start symbol
• > is the tape end symbol
• L(M) = {w ∈Σ∗ | M accepts w}
• Tape = <0011101001001110100100111010011111111010010011101001001110100111BBBBBBBMBBBBBBB>
• IR/W = Read/Write input string
• R/W = Read/Write
• A = Accepting state
• Qa = accept answer
• Qr = reject answer
• R = Move Right
• Q =
• {
•     {
•         (IR/W,<)=(IR/W,<,R),
•         (IR/W,0)=(IR/W,0,R),
•         (IR/W,1)=(IR/W,1,R),
•         (IR/W,B)=(IR/W,B,R),
•         (IR/W,M)=(IR/W,>,L to <)
•     }, {
•         (R/W,<)=(R/W,<,R to M),
•         (R/W,B)=(R/W,B,R),
•         (R/W,0)=(R/W,0,R),
•         (R/W,1)=(R/W,1,R),
•         (R/W,>)=(R/W,>,L to <)
•     }, {
•         (A,<)=(A,<,R to M),
•         (A,B)=(A,B,R),
•         (A,0)=(A,0,Qa),
•         (A,1)=(A,1,Qa),
•         (A,>)=(A,>,Qr)
•     }
• }
• M = ({{(IR/W,<)=(IR/W,<,R),(IR/W,0)=(IR/W,0,R),(IR/W,1)=(IR/W,1,R),(IR/W,B)=(IR/W,B,R),(IR/W,M)=(IR/W,>,L to <)}, {(R/W,<)=(R/W,<,R to M),(R/W,B)=(R/W,B,R),(R/W,0)=(R/W,0,R),(R/W,1)=(R/W,1,R),(R/W,>)=(R/W,>,L to <)}, {(A,<)=(A,<,R to M),(A,B)=(A,B,R),(A,0)=(A,0,Qa),(A,1)=(A,1,Qa),(A,>)=(A,>,Qr)}},{0,1},{0,1,<,>,B,M},{Q × Γ → Q × Γ × {L,R}},<,B,{>})

Non-deterministic turing machines may appear faster at the start. They allow you to easily seek and write data. This in itself is a fundamental weakness of the NDTM in that if I have a really long tape I have to rewind the tape the whole way back to where I want to change each and every time. Edited April 27, 2017 by fiveworlds

[Frank Vega Delgado]

fiveworlds, I have lost the connection between your arguments and the idea of the paper...

 

However, thanks for your comment...

[fiveworlds]

I have described a deterministic turing machine that calculated SAT it was called Colossus II. All of these turing machines were destroyed after ww2 and represented the pinnacle of turing machines at the time.

 

The MK II Colossus incorporated a new feature, Multiple Testing, which gave it a five fold increase in speed for setting wheels and rectangling to break patterns.

This was achieved by "remembering" selected bit streams 1. 2. 3 and 4 bits back from the current bit. Then as each character was read from the paper tape, the Z stream, the selected algorithm could be evaluated five times, all in parallel and the results counted into five counters. The bit stream being "remembered" could then be stepped on five start positions and the results in the five counters printed.

This was the first known use of what we now call a shift register.