Download PDFOpen PDF in browser

A Class of Examples Demonstrating That “P ≠ NP” in the “P Vs NP” Problem

EasyChair Preprint no. 3198

19 pagesDate: April 19, 2020


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.

Keyphrases: computation time, Kochen-Specker theorem, P vs NP, quantum computer, quantum computer as a Turing machine generalization, Turing machine

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
  author = {Vasil Penchev},
  title = {A Class of Examples Demonstrating That “P ≠ NP” in the “P Vs NP” Problem},
  howpublished = {EasyChair Preprint no. 3198},

  year = {EasyChair, 2020}}
Download PDFOpen PDF in browser