The proof that ℙ≠ℕℙ is likely 'established'.. I waited one day fixing possible
errors before the post for review. There should still be some missed.
Anything unclear or suggestions?
I would like also to demonstrate that C/C++ (or other potential language) should
probably notice that the programming language could (and should at least support)
serve as the basic tool for theories, including mathematics and computation
theory. Especially for C/C++, something must be very solid. Otherwise, proof of
'correctness' would be illusion or limited.
----------------------------------------------------------------------------
This file is intended a proof that ℙ≠ℕℙ. The contents may be updated anytime.
https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download-----------------------------------------------------------------------------
Algorithmic problem::= Problems that can processed by asymptotic analysis..
ANP::= Another NP is a set defined as {q| q is a description of the algorithmic
decision problem that provides 1. A set of certificate data C 2. A P-time
verification method v 3. The answer of q is 'yes' iff there exists a
certificate c, c∈C, such that v(c) is true 4. q can be computed within
O(2^|q| steps. }.
More precisely, ANP hisis the set of problems that can be solved by the
following pseudo-C/C++ program anp_temp(n):
bool anp_temp(Problem q) { // Problem: Description of the problem
Certificate c,begin,end; // Certificate data can be accessed by
begin= get_begin_certificate(q); // iteration, at least.
end = get_end_certificate(q);
for(c=begin; c!=end; c=next(c)) { // O(2^|n|) loop (see Note2)
if(v(c)) return true; // v:Certificate->{true,false}, P-time
// verification function.
}
return false;
}
Note1: Relative to the Turing Machine language for ℕℙ, the reason using
pseudo-C/C++ is that 1.C-code (almost all programming language not
involving special hardware features) and TM language are
computationally interchangable. 2.It describes the problem more clearly
3.The result 'false' is visible 4. The verification method v(c) is
explicitly spedified as a P-time function 5.Easier for machine aided
verification.
Note2: The semantics of the for loop in anp_temp(n) includes nested loops for
sets like C=C1×C2×C3×...
Problem q::= Given a decipher machine f, ciphertext ctext and plaintext ptext,
and the computation of f(ctext,key) being in P-time, Problem q asks whether
or not a key exists such that f(ctext,key)==ptext.
This problem can be expressed by the following pseudo-C/C++ program:
typedef unsigned int UInt; // UInt: Arbitrary non-negative integer
typedef UInt (*Func)(UInt,UInt); // Decipher function
bool key_exist(Func f, UInt ctext, UInt ptext) {
UInt key, begin, max;
begin= 0;
max = Limits<UInt>::Max-1; // max. value of key. *This value is preset*.
for(key=begin; key<=max; ++key) {
if(f(ctext,key)==ptext) return true;
}
return false;
}
Prop1: Problem q∈ANP
Proof: 1.The set of key maps the set of the certificate in the definition of
ANP 2.The computation of decipher machine f is in P-time 3.Others fit
the requirements of ANP...
Prop2: Problem q∉ℙ
Proof: Owing to the fact that the given arguments of key_exist(..) may
contain no any static information about the key (except the preset
range): The function f may be merely an interpreter, and every
possible key may be independent (i.e. whether or not x is a key is
irrelavent to that of another key y). If no more information of the
key is given, the computation of key_exist(..) can only be done by
visiting each one of O(2^|ctext|) possibilies of the key. Therefore,
the computation of the Problem q cannot be guaranteed in P-time.
From the results that Problem q∈ANP and Problem q∉ℙ, we can deduce ANP≠ℙ.
If ANP⊆ℕℙ, we can conclude ℙ≠ℕℙ.
+------+
| Test |
+------+
/*
C++ Test program: Using key_exist(..) to solve Subset Sum problem. Meanwhile,
Problem q∈ℕℙℂ is proved.
*/
#include <Wy.stdio.h>
using namespace Wy;
typedef uint32_t UInt;
typedef UInt (*Func)(UInt,UInt);
// [Syn] Test whether a key exists such that f(ctxt,key)==ptxt
// (Func f is assumed a P-time function)
//
// [Ret] true: ∃key, 0<=key<=max, f(ctxt,key)==ptxt
// false: Otherwise
//
bool key_exist(Func f, UInt ctxt, UInt ptxt) {
UInt key, begin, max;
begin=0;
max= Limits<UInt>::Max-1; // max is a preset value
for(key=begin; key<=max; ++key) {
if(f(ctxt,key)==ptxt) {
return true;
}
}
return false;
};
// [Syn] Class Set encodes a small set of unsigned char in UInt.
// (Impl. note: At most 3 elements. Value range= [0,255])
//
class Set {
static constexpr UInt FieldBits=8;
UInt m_val; // Each element occupies 8-bits (from bit8, bit0=num of elems)
public:
typedef unsigned char ElemType;
Set() : m_val(0) {};
Set(const Set& s) : m_val(s.m_val) {};
explicit Set(UInt val) : m_val(val) {};
explicit operator const UInt&() const { return m_val; };
bool is_default() const { return m_val==0; };
UInt num_elements() const { return m_val&0xff; };
bool is_valid() const {
UInt n_elem= num_elements();
if(n_elem==0) { // Check 1.n_elem in range [0,3] 2.Each element
return m_val==0; // is unique 3.Others
} else if(n_elem==1) {
if(m_val&0xffff0000) {
return false;
}
} else if(n_elem==2) {
if(m_val&0xff000000) {
return false;
}
ElemType a0= (m_val&0x0000ff00)>>FieldBits;
if(a0==(m_val&0x00ff0000)>>(2*FieldBits)) {
return false;
}
} else if(n_elem==3) {
const ElemType a0= (m_val&0x0000ff00)>>FieldBits;
const ElemType a1= (m_val&0x00ff0000)>>(2*FieldBits);
const ElemType a2= (m_val&0xff000000)>>(3*FieldBits);
if((a0==a1)||(a0==a2)||(a1==a2)) {
return false;
}
} else {
return false;
}
return true;
};
bool contain(ElemType elem) const {
switch(num_elements()) {
case 0: return false;
case 1: return elem==(m_val&0x0000ff00)>>FieldBits;
case 2: return (elem==(m_val&0x0000ff00)>>FieldBits)||
(elem==(m_val&0x00ff0000)>>(2*FieldBits));
case 3: return (elem==(m_val&0x0000ff00)>>FieldBits)||
(elem==(m_val&0x00ff0000)>>(2*FieldBits))||
(elem==(m_val&0xff000000)>>(3*FieldBits));
default: WY_THROW( Errno() );
};
};
ElemType element(UInt idx) const {
if((idx>=3)||(idx>=num_elements())) {
WY_THROW( Errno(EINVAL) );
}
switch(idx) {
case 0: return (m_val&0x0000ff00)>>FieldBits;
case 1: return (m_val&0x00ff0000)>>(2*FieldBits);
default: // assert(idx==2)
return (m_val&0xff000000)>>(3*FieldBits);
}
};
void reset() { m_val=0; };
void reset(const Set& s) { m_val=s.m_val; };
Set& operator =(const Set& s) { m_val=s.m_val; return *this; };
void _set_element(ElemType e0) { m_val=(e0<<FieldBits)+1; };
void _set_element(ElemType e0, ElemType e1) {
m_val=e1;
m_val<<=FieldBits; m_val+=e0;
m_val<<=FieldBits; m_val+=2;
};
void _set_element(ElemType e0, ElemType e1, ElemType e2) {
m_val=e2;
m_val<<=FieldBits; m_val+=e1;
m_val<<=FieldBits; m_val+=e0;
m_val<<=FieldBits; m_val+=3;
};
};
static_assert(sizeof(Set)==sizeof(UInt));
static_assert(sizeof(Set)==4);
// [Syn] Get plaintext from ciphertext and the key
//
// [Ret] Plaintext converted from ciphertext ctxt and the key, or
// InvPText= Invalid Argument (invalid value of plaintext)
//
constexpr UInt InvPText= ~(UInt)0;
UInt decipher(UInt ctxt, UInt key) { // Return plaintext
const Set majset(ctxt), subset(key); // Convert ctxt/key to sets
if(majset.is_valid()==false) {
return InvPText;
}
if(subset.is_valid()==false) {
return InvPText;
}
const UInt n_elem= subset.num_elements();
if(n_elem>majset.num_elements()) {
return InvPText;
}
UInt sum=0;
if(n_elem==0) {
return 0;
} else if(n_elem==1) {
Set::ElemType elem= subset.element(0);
if(majset.contain(elem)==false) {
return InvPText;
}
sum= elem;
} else if(n_elem==2) {
Set::ElemType elem= subset.element(0);
if(majset.contain(elem)==false) {
return InvPText;
}
sum= elem;
elem= subset.element(1);
if(majset.contain(elem)==false) {
return InvPText;
}
sum+= elem;
} else if(n_elem==3) {
Set::ElemType elem= subset.element(0);
if(majset.contain(elem)==false) {
return InvPText;
}
sum= elem;
elem= subset.element(1);
if(majset.contain(elem)==false) {
return InvPText;
}
sum+= elem;
elem= subset.element(2);
if(majset.contain(elem)==false) {
return InvPText;
}
sum+= elem;
} else {
return InvPText;
}
return sum;
};
// [Syn] Compute a small Subset Sum problem by using key_exist(..)
//
// [Ret] true: A subset that the sum of its elements is equal to $sum exists
// false: Otherwise
//
bool subset_sum(Set set, UInt sum) {
// decipher(ctext,key)->ptext
// ctext= $set (set can be directly converted/cast to ciphertext)
// ptext= $sum (sum can be directly converted/cast to plaintext)
// key = $subset
return key_exist(decipher,static_cast<UInt>(set),sum);
};
---------------------------------------------------------------------------
ℙ≠ℕℙ proof
Re: ℙ≠ℕℙ proof