Jump to content

I have an NP-complete algorithm, under the assumption that P=NP


porton

I found no errors after checking  

  1. 1. I found no errors after checking

    • Yes
      0
    • No
      0
    • I didn't read
      0
    • I read but don't understand
      0


Recommended Posts

I claim to have proved that my algorithm is NP-complete under the assumption that P=NP.

https://math.portonvictor.org/2021/04/08/my-algorithm-that-is-np-complete-in-the-case-if-pnp/

Please, check my proof for errors (3 pages PDF file with the proof itself fitting in 1 page).

That's the third revision of my algorithm. The first two were erroneous.

This is my first math research work outside of general topology (and some logic/CS stuff far from complexity theory). I did it in about two days.

I don't know how to break BitCoin, surely my algorithm is slow.

BTW, which prizes to expect?

Edited by porton
typo
Link to comment
Share on other sites

Sorry, next to total ignorant here.

The Millennium Prize is on proving P=NP. I assume that's what you're aiming for:

21 minutes ago, porton said:

BTW, which prizes to expect?

(My emphasis.)

Isn't assuming P=NP kind of begging the question?

Link to comment
Share on other sites

33 minutes ago, porton said:

Please, check my proof for errors (3 pages PDF file with the proof itself fitting in 1 page).

Can you summarise the proof and attach the pdf as reference?

(The link just displays ads when I try to access)

Link to comment
Share on other sites

@joigus I didn't prove P=NP. I only proved some its consequence.

If they to split their million, my discovery is 1/2. But they reward only a complete solution of the entire problem.

18 minutes ago, Ghideon said:

Can you summarise the proof and attach the pdf as reference?

(The link just displays ads when I try to access)

I won't attach the PDF for licensing issues. The link to PDF: https://math.portonvictor.org/wp-content/uploads/2021/04/np-complete-3.pdf (better indeed use the indirect link above, as the direct PDF link may be updated to a new version of my text from time to time).

The algorithm:

Let R(X) be the property, whether an arbitrary algorithm X (that takes any input data Y) produces a proof (in a certain formal system) of the statement (for every algorithm Y)
X(Y) = Z ⇒ ∃algorithm X' : X' (Z) = Y.

In other words, R(X) is provability of invertibility of an algorithm X.

R(X) has the convenient property that it is decidable and moreover always provable to be either true or false.

The algorithm V(A) means to run algorithm A and then check if the result of A is a logical proof of either R(X) or ¬R(X).

R(X) on { X | R(X) or ¬R(X) } is an NP-complete problem. Here is its NP-complete (if P=NP) solution:

Enumerating all algorithms An (n ∈ N) run the algorithms V(An) on X in parallel (interleaving these algorithms, and before each step n of the loop adding An to our dynamic array of algorithms) until one of the “threads” F produces “true” or “false” (not “unknown”) (thus having a proof of R(X) or a proof of ¬R(X)).

The bold algorithm halts and solves any problem in { X | R(X) or ¬R(X) } because by the assumption some An is NP-complete.

Then I prove that the bold algorithm is polynomial-time using the assumption (P=NP) that some algorithm An that produces true or false is polynomial-time.

BTW, when for an experiment I removed ads for some time, I didn't decrease bounce rate of my site (however I don't really earn on ads anyway).

Edited by porton
Link to comment
Share on other sites

6 hours ago, porton said:

I only proved some its consequence.

This isn't my area of expertise but I'm curious: How does your result differ from known properties of other NPC problems? What are the specific consequences that does not show up in for instance SAT** or others?   

If I recall correctly: under the assumption that [math]P=NP [/math] it follows that [math] NPC \approx NP=P [/math]. if any NP-complete problem can be solved quickly*, then every problem in NP can. Every problem in NP must be reducible to every NP-complete problem in polynomial time. Hence all NP-complete problems share properties; there needs to be something fundamentally new to claim such a prize? 

(Note: The title of the thread is not clear; problems are NP-complete, not algorithms.)

*) Quickly=polynomial time. It is not known if P=NP, as @joigus said no proof exists yet.
**) 
Cook–Levin theorem,  Boolean satisfiability problem

Edited by Ghideon
latex tags. Note about thread title
Link to comment
Share on other sites

6 hours ago, porton said:

@joigus I didn't prove P=NP. I only proved some its consequence.

 

That's what I'm worried about. You proved some of its consequences if P=NP is true. IOW, it only means P=NP cannot be disproved --within your logical frame-- by reductio ad absurdum. But nothing else. That's called "begging the question."

I'm not at the level of @Ghideon in these matters, I'm just telling you that you should be aware of this possible flaw. If you're aiming for the stars, you should point at them.

I take it that your saying,

7 hours ago, porton said:

BTW, which prizes to expect?

was a joke. You may be on to something interesting after all. Even if it's not a proof of P=NP. I'll take a back sit and try to learn something.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.