What's wrong with my P = NP proof?

[Frank Vega]

Hi!! I need help!! I'm trying to solve the P versus NP problem and I've found a solution that seems pretty easy to follow and understand.

 

I will share you the paper in the attachment of this post!!!

 

However, I shared this paper to an Italian colleague and he told me there is one error in Theorem 3.5, but he didn't want to tell where the error is. But, I'm pretty sure that result is correct. I'm Bachelor of Computer Science and I work as computer programmer in Belgrade, so there are not so much people in which I can find an aid. On the one hand, it is a waste of time trying to email for some of the theoretical experts asking for help because they are saturated of such claiming of wrong proof about P versus NP. On the other hand, if I submit this paper to a journal, then I should wait perhaps 6 or 24 months to have a revision of my paper, and in many cases, those journals have P versus NP handling policies.

 

Could you help me, please?

Regards,

Frank.

pvsnp-hal.pdf

Edited July 16, 2016 by Frank Vega

[John Cuthber]

"What's wrong with my P = NP proof?"

The first thing that's wrong is that we can't see it.

That puts it in breach of the rules you signed up to when you joined

They say

"and members should be able to participate in the discussion without clicking any links or watching any videos. "

Please post a copy of the proof- or at least some sort of summary, here where we can discuss it.

[Frank Vega]

Thank you very much. I have shared the paper as an attachment of this post and I removed the link.

[DevilSolution]

Hi, i havent read through your whole paper as time is limited, however just to clarify the complexity of an algorithm defined by the theoretical time taken to compute said algorithm isnt the process of logical deduction but the inferred solution to the algorithm itself.

 

Just for example P != NP for any problem where we cannot pre-determain how many iterations the solution must iterate or recur. When we know such a solution exists by how many iterations then the solution is deduction but when the solution is not known we can only infer a "best case". This is regardless of notation or abstraction. You can sometimes tailor an algorthm to give such results hence deducing the solution but some problems have no simplification other than brute force or such.....

Can you prove P = NP via SAT? Although most see the traveling salesman as prime candidate for proof, i think any SAT solver to = P would be the most effective proof.

[Frank Vega]

You are right: a polynomial time algorithm for SAT will be the most elegant and practical solution. Unfortunately, my proof is basically theoretical, so you cannot solve feasibly an NP-complete problem using my proof. However, this could show it is possible to find such polynomial algorithms for the NP-complete problems: maybe in the near future if this proof is correct.

Edited July 17, 2016 by Frank Vega

[Frank Vega]

The Italian colleage told me he had a misunderstood. He didn't want to tell me his explanation of his error because he wanted that I take it as an exercise. However, this is not a guarantee that my proof is correct. If you find a truly error in my proof, don't hesitate to share it!!!!

Edited July 28, 2016 by Frank Vega

[fiveworlds]

Here

 

Definition 1.3. NP is the class of languages that have polynomial time verifiers

 

Not specifically true. NP "non-deterministic polynomial time" was defined in terms of non-deterministic machines (machines that have more than one possible move from a given configuration for a particular input). P "deterministic polynomial time" was defined in terms of deterministic machines (machines that only have one possible configuration for a particular input).

 

The problem goes on to state that you may define the class NP of languages by the condition that a language
L over Σ is in NP iff there is k ∈ N and a polynomial-time checking relation R such that for all w ∈ Σ∗ ,
w ∈ L ⇐⇒∃y (|y|≤|w|k and R (w, y)),
where |w| and |y| denote the lengths of w and y, respectively.

 

You are also given from their problem statement that P is obviously less than or equal to NP.

[Frank Vega]

I suggest you should take a look to the page "NP (complexity)" in Wikipedia. Here is the link:

 

https://en.wikipedia.org/wiki/NP_%28complexity%29

 

You will see there the following statements in the section "Formal definition":

 

"Alternatively, NP can be defined using deterministic Turing machines as verifiers. A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that

• For all x and y, the machine M runs in time p(|x|) on input (x,y)
• For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
• For all x not in L and all strings y of length q(|x|), M(x,y) = 0"

Alternatively, I suggest to read some serious books that appears in the reference of my paper.

[fiveworlds]

Did you read Stephen Cook's webpage?? https://www.cs.toronto.edu/~sacook/#publications

 

He states in his paper https://www.cs.toronto.edu/~sacook/math_teachers.pdf

 

That all he expects for P=NP is the solution to one NP-complete problem. So if you just wrote SAT then P=NP.

 

SAT is I find the easiest of the NP-Complete problems because all we need do is trade resources for time. Is there a case where a Boolean expression evaluates to true.We can trade resources for time in this case with sufficient resources (And Or and Not) gates setup in an array configuration we can the place a large Or gate on the output which evaluates to true if any of the Boolean expressions evaluate to true in polynomial time for a finite size input.

 

Since there is only so many resources in the universe you should look at ways to reduce the problem to simpler forms for instance

cases with

 

((¬b And b)∧z)

 

are only true if y is true so you should be able to read that string and know that it is equivalent to

 

z

 

Since I have already written the Boolean satisfiability problem in polynomial time you can have a look at how I did it.

<?php
////booleanexpression = "(a AND b) OR (NOT C AND D)";

function evaluate_boolean($output,$lettera,$letterb,$switch)
{    
    if($switch){
        // condition where input is a result of a previous boolean expression which is always false/true
        if($lettera === "FALSE" AND $letterb === "FALSE"){
            if($letterb === "FALSE"){
                $output = preg_replace("/{$lettera} AND NOT {$letterb}/", "FALSE", preg_replace("/NOT {$lettera} AND {$letterb}/", "FALSE", preg_replace("/{$lettera} OR {$letterb}/", "FALSE", $output)));
            }
            else{
                $output = preg_replace("/NOT {$lettera} AND NOT {$letterb}/", "FALSE", preg_replace("/{$lettera} AND {$letterb}/", "FALSE", preg_replace("/{$lettera} OR NOT {$letterb}/", "FALSE", $output)));
            }
        }
        else{
            if($letterb === "FALSE"){
                $output = preg_replace("/NOT {$lettera} AND NOT {$letterb}/", "FALSE", preg_replace("/{$lettera} AND {$letterb}/", "FALSE", preg_replace("/NOT {$lettera} OR {$letterb}/", "FALSE", $output)));        
            }
            else{
                $output = preg_replace("/NOT {$lettera} AND {$letterb}/", "FALSE", preg_replace("/{$lettera} AND NOT {$letterb}/", "FALSE", preg_replace("/NOT {$lettera} OR NOT {$letterb}/", "FALSE", $output)));    
            }
        }
    
        if ($output !== "FALSE"){$output =  "TRUE";}    
    }
    else
    {    
        if($lettera === $letterb){
            $output = preg_replace("/{$lettera} AND NOT {$letterb}/", "FALSE", preg_replace("/NOT {$lettera} AND {$letterb}/", "FALSE", $output));    
        }
        
        if ($output !== "FALSE"){
            $output =  "TRUE";
        }        
    }
    
    return $output;
}

$output = evaluate_boolean('a AND b',"a","b",FALSE);
$output2 = evaluate_boolean('NOT c AND d',"c","d",FALSE);
$resultant = evaluate_boolean("{$output} OR {$output2}","{$output}","{$output2}",TRUE);
echo $output2;


?>

Edited July 31, 2016 by fiveworlds

[Strange]

 

Since I have already written the Boolean satisfiability problem in polynomial time you can have a look at how I did it.

 

I would like to see the proof of that.

[fiveworlds]

I would like to see the proof of that.

 

Did you run the PHP? That works but it doesn't work for instances allowing for the same variable. Here is a similar function allowing for instances of the same variable. Allowing instance of the same variable makes the problem harder but it still runs in polynomial time.

<?php
////booleanexpression = "(a AND b) OR (NOT C AND D)";

function evaluate_boolean($output,$lettera,$letterb,$switch,$previouslettera = NULL,$previousletterb = NULL,$previousletterc = NULL,$previousletterd = NULL,$fullexpression = NULL)
{    
    if($switch){
        
        //check if letters from boolean expressions are the same
        if($previouslettera === $previousletterc || $previouslettera === $previousletterd || $previousletterb === $previousletterc || $previousletterb === $previousletterd){
            $output = preg_replace(
            array(
                "/{$previouslettera} AND {$previousletterb} AND NOT {$previouslettera} AND {$previousletterd}/",
                "/{$previouslettera} AND {$previousletterb} AND {$previousletterc} AND NOT {$previouslettera}/",
                "/{$previouslettera} AND {$previousletterb} AND NOT {$previousletterb} AND {$previousletterd}/",
                "/{$previouslettera} AND {$previousletterb} AND {$previousletterc} AND NOT {$previousletterb}/",
                "/NOT {$previouslettera} AND {$previousletterb} AND {$previouslettera} AND {$previousletterd}/",
                "/NOT {$previouslettera} AND {$previousletterb} AND {$previousletterc} AND {$previouslettera}/",
                "/{$previouslettera} AND NOT {$previousletterb} AND {$previousletterc} AND {$previousletterb}/",
                "/{$previouslettera} AND NOT {$previousletterb} AND {$previousletterb} AND {$previousletterd}/"        
            ),"FALSE",$fullexpression);
        }        
        
        // condition where input is a result of a previous boolean expression which is always false/true
        if($lettera === "FALSE" AND $letterb === "FALSE"){
            if($letterb === "FALSE"){
                $output = preg_replace(
                array(
                    "/{$lettera} AND NOT {$letterb}/",
                    "/NOT {$lettera} AND {$letterb}/",
                    "/{$lettera} OR {$letterb}/"
                ), "FALSE", $output);
            }
            else{
                $output = preg_replace(
                array(
                    "/NOT {$lettera} AND NOT {$letterb}/",
                    "/{$lettera} AND {$letterb}/",
                    "/{$lettera} OR NOT {$letterb}/"
                ), "FALSE", $output);
            }
        }
        else{
            if($letterb === "FALSE"){
                $output = preg_replace(
                array(
                    "/NOT {$lettera} AND NOT {$letterb}/",
                    "/{$lettera} AND {$letterb}/",
                    "/NOT {$lettera} OR {$letterb}/"), "FALSE", $output);        
            }
            else{
                $output = preg_replace(
                array(
                    "/NOT {$lettera} AND {$letterb}/",
                    "/{$lettera} AND NOT {$letterb}/",
                    "/NOT {$lettera} OR NOT {$letterb}/"), "FALSE", $output);    
            }
        }
    
        if ($output !== "FALSE"){$output =  "TRUE";}    
    }
    else
    {    
        if($lettera === $letterb){
            $output = preg_replace(
            array(
                "/{$lettera} AND NOT {$letterb}/",
                "/NOT {$lettera} AND {$letterb}/"), "FALSE", $output);    
        }
        
        if ($output !== "FALSE"){
            $output =  "TRUE";
        }        
    }
    
    return $output;
}

$output = evaluate_boolean('a AND b',"a","b",FALSE);
$output2 = evaluate_boolean('NOT a AND d',"a","d",FALSE);
$resultant = evaluate_boolean("{$output} OR {$output2}","{$output}","{$output2}",TRUE,"a","b","a","d","a AND b AND NOT a AND d");
echo $resultant;


?>

Incorporating validation would mean that if I wrote a solution to SAT in polynomial time for 50 variables I could run check if any expression smaller than 50 variables evaluated to true however if I wanted 51 I would have to rewrite the entire algorithm... Sigh I could probably use arrays and array_unique to generate the tests in polynomial time..

Edited July 31, 2016 by fiveworlds

[Strange]

 

Did you run the PHP?

 

 

I said proof, not example.

 

Please show how you calculate the run time (O(n)) in terms of the problem size.

[fiveworlds]

Please show how you calculate the run time (O(n)) in terms of the problem size

 

For the above algorithm for any given input it will run the if statements. There isn't any looping so it can't get any harder or less hard for a set maximum input size. Also you can trade resources for time in this case you can run all the checks at once so it runs in (O(n)) time. The annoying thing is that when increasing the maximum input size the resources required for verification of the same element this bit.

 if($previouslettera === $previousletterc || $previouslettera === $previousletterd || $previousletterb === $previousletterc || $previousletterb === $previousletterd){
            $output = preg_replace(
            array(
                "/{$previouslettera} AND {$previousletterb} AND NOT {$previouslettera} AND {$previousletterd}/",
                "/{$previouslettera} AND {$previousletterb} AND {$previousletterc} AND NOT {$previouslettera}/",
                "/{$previouslettera} AND {$previousletterb} AND NOT {$previousletterb} AND {$previousletterd}/",
                "/{$previouslettera} AND {$previousletterb} AND {$previousletterc} AND NOT {$previousletterb}/",
                "/NOT {$previouslettera} AND {$previousletterb} AND {$previouslettera} AND {$previousletterd}/",
                "/NOT {$previouslettera} AND {$previousletterb} AND {$previousletterc} AND {$previouslettera}/",
                "/{$previouslettera} AND NOT {$previousletterb} AND {$previousletterc} AND {$previousletterb}/",
                "/{$previouslettera} AND NOT {$previousletterb} AND {$previousletterb} AND {$previousletterd}/"        
            ),"FALSE",$fullexpression);
        } 

increase at a rate of 2^!(n)/2. It doesn't take more time to run the checks however if we have the resources to run them. Without the need for verifying if there are duplicate values it will require less resources/memory to run. Yes that is a factorial in there so it isn't O(n^k) complexity for one and I don't see it making a difference if it was non-deterministic machine at higher numbers either. By the way the option of using a circuit AND OR and NOT to reduce the problem is known as Circuit SAT. The main difference between my algorithm and circuit SAT (NP) which make mine in P are that rather than testing every possible option I am testing for instance of a search Boolean string known to always evaluate to False. On every other occasion not containing the search string (linear search) https://en.wikipedia.org/wiki/Linear_search it is possible for the algorithm to evaluate to true. Checking for a given search string is in P.

Edited July 31, 2016 by fiveworlds

[fiveworlds]

This is the reduced version written as a circuit similar to an Adder but it has 3 binary inputs. The circuit version doesn't have the same complexity problems at all.

 

Values always false

NOT TRUE AND TRUE
TRUE AND NOT TRUE
NOT TRUE OR NOT TRUE
NOT FALSE AND NOT FALSE
NOT TRUE AND NOT FALSE
FALSE AND FALSE

Values always false as a binary circuit

SWITCH
A 11101 1
B 01110 1
C 11011 1
D 10111 1
E 11110 1
F 00100 1

Input 6 digits

g , h , i , j , k , l
0 , FALSE , OR , , FALSE , SWITCH OFF
1 NOT, TRUE , AND ,NOT , TRUE , SWITCH ON


switch is only on iff both h and k are carries in (known always true/false values)

if (NOT((A === input) OR (B === input) OR (C === input) OR (D === input) OR (E === input) OR (F === input))){
return FALSE
}

Here we AND the bits in the binary input with A,B,C,D,E,F and if any of them are the same it will output true and then not the output.

Edited August 3, 2016 by fiveworlds

[Frank Vega]

I hope your proof were correct. Unfortunately, my proof has a flaw. Thank you for your comments!!!

[Rilegatore]

I recommend you to read the recently published work of Russian professor, which contains algorithm of translation general 3-SAT formula to the conjunction of two logic functions. For each of this functions you can find a solution in polynomial time. This does not mean equality of classes P and NP.

Currently, the State University analyses this work.

Try searching for keywords "SLS", "2.5-SAT" and "NP=P+P".