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

[porton]

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 April 9, 2021 by porton
typo

[joigus]

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?

[Ghideon]

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)

[porton]

@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 April 9, 2021 by porton

[Ghideon]

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 April 9, 2021 by Ghideon
latex tags. Note about thread title

[joigus]

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.