Vasil Penchev
Bulgarian Academy of Sciences
The CMI Millennium “P vs NP Problem” can be resolved e.g. if one shows at least one counterexample to the "P = NP" conjecture. A certain class of problems being such counterexamples will be formulated. This implies the rejection of the hypothesis that "P = NP" for any conditions satisfying the formulation of the problem. Thus, the solution "P is different from NP" of the problem in general is proved. The class of counterexamples can be interpreted as any quantum superposition of any finite set of quantum states. The Kochen-Specker theorem is involved. Any fundamentally random choice among a finite set of alternatives belong to "NP" but not to "P". The conjecture that the set complement of "P" to "NP" can be described by that kind of choice exhaustively is formulated.
Keywords Kochen - Specker theorem  P vs NP  Turing machine  computation time  quantum computer as a Turing machine generalization
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Quantum Computer: Quantum Model and Reality.Vasil Penchev - 2020 - Epistemology eJournal (Elsevier: SSRN) 13 (17):1-7.
Contextualism and Nonlocality in Quantum Mechanics.Michael William Kernaghan - 1995 - Dissertation, The University of Western Ontario (Canada)
Conway–Kochen and the Finite Precision Loophole.Ronnie Hermens - 2014 - Foundations of Physics 44 (10):1038-1048.
Infinite Time Turing Machines With Only One Tape.D. E. Seabold & J. D. Hamkins - 2001 - Mathematical Logic Quarterly 47 (2):271-287.
Representation and Reality by Language: How to Make a Home Quantum Computer?Vasil Penchev - 2020 - Philosophy of Science eJournal (Elsevier: SSRN) 13 (34):1-14.
A Mathematical Model of Quantum Computer by Both Arithmetic and Set Theory.Vasil Penchev - 2020 - Information Theory and Research eJournal 1 (15):1-13.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Schütte's Tautology and the Kochen-Specker Theorem.Jeffrey Bub - 1996 - Foundations of Physics 26 (6):787-806.


Added to PP index

Total views
107 ( #103,857 of 2,462,431 )

Recent downloads (6 months)
52 ( #16,543 of 2,462,431 )

How can I increase my downloads?


My notes