Independence of P vs. NP in regards to oracle relativizations

a r

X

i

v

:08

5

.

2

1

7

v

4

[

c

s

.

C

C

]

2

1

M a

y

2

8

Independence of P vs.NP in regards to oracle relativizations.JERRALD MEEK 1.INTRODUCTION.Previously in “P is a proper subset of NP ”[Meek Article 1,2008]and “Analysis of the Deterministic Polynomial Time Solvability of the 0-1-Knapsack Problem”[Meek Article 2,2008]the present author has demonstrated that some NP-complete problems are likely to have no deterministic polynomial time solution.In this article the concepts of these previous works will be applied to the relativizations of the P vs.NP problem.By constructing examples of ?ve out of the six relativizing oracles from Baker,Gill,and Solovay [1975],it will be demonstrated that inconsistent relativizations do not preclude a proof of P =NP or P =NP .It will then become clear that the P vs.NP question is independent of oracle relativizations.2.PRELIMINARIES.Baker,Gill,and Solovay [1975]have previously shown that there are six types of oracles that can be constructed to examine the P vs.NP problem.These include (1)Oracle A such that P A =NP A .(2)Oracle B such that P B =NP B .

(3)Oracle C such that NP C is not closed under complementation.

(4)Oracle D such that P D =NP D but NP D is closed under complementation.

(5)Oracle E such that P E =NP E and P E =NP E ∩co-NP E .

(6)Oracle F such that P F ?[NP F ∩co-NP F ]?NP .

Theorem 4.4from P is a proper subset of NP .[Meek Article 1,2008]2.1.P =NP Optimization Theorem.

2·Jerrald Meek

The only deterministic optimization of a NP-complete problem that could prove P=NP would be one that can always solve a NP-complete problem by examining no more than a polynomial number of input sets for that problem.

De?nition2.1.Oracle Machine

An oracle machine can be deterministic or non deterministic.The di?erence between an oracle machine and a regular Turing Machine is that an oracle Machine has a yes state,a no state,and a query state.When the oracle machine is placed in the query state after passing a string to the oracle,if that string is an element of the oracle set,then the oracle will place the Turing Machine in the yes state,other wise it will place the Turing Machine in the no state.The processing time required by the oracle can be considered instantaneous.

2.1Encoding Methods.

In this article,two encoding methods will be used.One encoding method will encode the input sets for a problem and is identical to that used by Baker,Gill, and Solovay[1975].This will be identi?ed as“input encoding.”

The second method of encoding will be used to identify a partition of the set of all possible input sets for a problem.This method of encoding will be identi?ed as “partition encoding.”

2.1.1Partition Encoding.The concept of partition encoding is not to encode the input sets for a problem,but an entire partition of the set of all possible input sets.However,for this method to work the partitioning must be identi?ed with a speci?c problem.

The method of partition encoding used in this work will divide partitions by the number of literals in an input set which have a true value.If a problem has n literals,then there will be n+1partitions(one partition has no true literals). Notice that the problem[a∨b∨c]has di?erent input sets that result in true evaluations from the problem[?a∨b∨c]even though the cardinality of these input sets are equivalent.

It will then be necessary that the problem which a partition applies to will need to be encoded.This could be accomplished by representing a literal with a unique unary number terminated with a zero,then literal a is10,b is110,c is1110. The operators can be represented with a unary number that always starts with zero and ends with zero010represents open grouping operators{[,(,{,ect.}, 0110represents close grouping operators{],),},ect.},01110is the negation operator,011110is the inclusive or operator,0111110is the exclusive or operator, 01111110is the and operator,011111110is the equivalence operator,0111111110 is the inequality operator,ect.This encoding could then be extended in a similar manner to allow the encoding of all logical operators.

The encoding of the problem will be pre?xed by a unary number with a termi-nating0representing the number of true literals in the partition.

By this encoding method the partition of the problem[a∨b∨c]with1true literal could be represented by 10,010,10,011110,110,011110,1110,0110 ,while [?a∨b∨c]with2true literals could be represented by

110,010,01110,10,011110,110,011110,1110,0110

ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·3 3.THE RELATIVIZING ORACLES.

Baker,Gill,and Solovay[1975]have shown that the classes of P and NP do not relativize in a consistent manner.The inconsistency of the relativizations of P and NP has often been used to justify arguments that the P vs.NP problem is unusually di?cult at best,or maybe even impossible.

By slightly altering the machine model,we can obtain di?ering answers

to the relativized question.This suggests that resolving the original

question requires careful analysis of the computational power of ma-

chines.It seems unlikely that ordinary diagonalization methods are

adequate for producing an example of a language in NP but not in P;

such diagonalizations,we would expect,would apply equally well to the

relativized classes,implying a negative answer to all relativized P=?

NP questions,a contradiction.[Baker et al.,1975]

Although it is generally accepted that diagonalization is not an e?ective method for solving the P vs.NP problem,it is the purpose of this article to demonstrate that oracle relativizations in no way prevent a solution to the P vs.NP problem. It is also worthwhile to mention that the six oracles of Baker,Gill,and Solovay [1975]do not represent an exclusive set of all oracle relativizations.There has been extensive work to?nd other unusual relativizations of complexity classes in regards to the P vs.NP question.For example,Bennett and Gill[1981]have found that random oracles can produce the relativization P A=NP A=co-NP A.However,the scope of this work will be limited to the six oracles from Baker,Gill,and Solovay [1975]with the expectation that what is learned from these six oracles may be applied to any other relativizing oracle.

3.1A P=NP Oracle.

The P=NP Optimization Theorem requires that no more than a polynomial number of input sets can be examined by a deterministic polynomial time search algorithm.By the same logic it is obvious that a deterministic oracle machine can not request more than a polynomial number of queries in polynomial time. Baker,Gill,and Solovay[1975]de?ne the oracle A such that A={ i,x,0n : NP A i accepts x in

This de?nition produces an oracle such that P A=NP A.However,this de?nition does not really say anything about how the oracle functions.In this work,the oracle will be created by partition encoding strings,a string will be included in oracle A if there exists at least one element of the partition represented by the string which results in the problem associated to the string evaluating true.

—Let L(X)={x:there exists y∈X such that|y|=|x|}for any oracle X.—Let x be the set of all problems in L(X).

—Let S be the set such that S i is the set of all possible input sets for x i when 1≤i≤|x|.

The oracle set is created by the following algorithm.

(1)Let i=1.

(2)Let e=1.

ArXiv,Vol.V,No.N,Month20YY.

4·Jerrald Meek

(3)If x i evaluates true with input S i

e ,then add the partition encoding o

f S i

e

→x i

to set A,and let e=|S i|.

(4)If e<|S i|,then increment e and continue at step3.

(5)If e=|S i|and i<|x|,then increment i and continue at step2.

(6)If e=|S i|and i=|x|,then the set A has been found.

The goal was to produce an example of an oracle set such that P A=NP A.Here, the oracle A is actually such that P A=NP.Such an oracle would also create the condition that P A=NP A.Another method could be used to create an oracle such that P X=PSPACE,which would also satisfy P X=NP X,except that NP= NP X.There are multiple such oracles,however according to Mehlhorn[1973]the set of computable oracles such that P A=NP A is meager.

Notice that in this example the set of all possible input sets will be exponential in size,and therefore some partitions for any problem will be exponential in size. It is then easy to see that the problem of creating the oracle set(even when the oracle is created to only work for one problem)is a member of the FNP complexity class(when P A=NP).

The process that a Deterministic Oracle Machine with oracle set A uses to solve problem x i which is in NP and has n literals is the algorithm.

(1)Let e=0.

(2)Encode the partition for problem x i for input sets having e true literals.

(3)Pass the partition encoding from step2to the oracle and enter the query state.

(4)If the machine is in the yes state then halt in an accepting state.

(5)If the machine is in the no state and e

step2.

(6)If the machine is in the no state and e=n then halt in a non-accepting state. The algorithm of the oracle machine solves any NP problem in polynomial time on a Deterministic Oracle Machine.A Non Deterministic Oracle Machine could also use this algorithm to solve the same set of problems in polynomial time.Therefore, P A=NP A.

This method is dependant on an oracle set creation algorithm requiring deter-ministic exponential time for each problem that the oracle is capable of solving.If so desired,the time required to compute the oracle set could be treated as separate to the process of solving the problem.

Another option is that the Deterministic Oracle Machine could be networked to both an oracle and a Non Deterministic Turing Machine.In this model the non deterministic machine generates the oracle set which it sends to the oracle.This method will allow the entire process to require polynomial time.

A third method is that we simply assume that the oracle set somehow creates itself magically.

Regardless of the method used to generate the oracle set,all three methods involve somehow concealing the majority of the work.This does not in any way reduce the complexity of the problem;it only removes the di?culty of the problem by placing the majority of the computational burden upon the process of oracle set creation.

ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·5

In this example the oracle A was created such that P A=NP.It would have been valid to create oracle set A such that P A=PSPACE.However,it can not be expected that such an oracle would be any easier to create.

3.2A P=NP Oracle.

The method of producing oracle set B as described by Baker,Gill,and Solovay [1975]is similar to the algorithm:

—Let L(X)={x:there exists y∈X such that|y|=|x|}for any oracle X.—Let x be the set of all problems in L(X).

—Let S be the set such that S i is the set of all possible input sets for x i when 1≤i≤|x|.

—Let B(i)represent the elements of B placed in B prior to stage i.

—Let p i(n)<|S i|be a polynomial function of n that represents the number of computations preformed by P X i and NP X i for all oracles X.If p i(n)computations have been preformed,and no accepting element of S i has been found,then the algorithm halts in the non-accepting state without examining all elements of S i. Create the oracle with the algorithm.

(1)Let i=1.

(2)If P B i(i)rejects x i then the next unexamined element of S i is an element of B.

(3)If i<|x|then increment i and continue at step2.

(4)If i=|x|then the oracle set B has been found.

The process used by an oracle machine with oracle set B for?nding a solution to a problem x i in NP with n i literals is preformed by the following algorithm. (1)Search for an element of S i which results in x i evaluating true.Terminate the

search if the time limit p i(n)has been reached.

(2)If a solution to x i was found then,halt in an accepting state.

(3)If no solution to x i was found and all elements of S i were examined in step1,

then halt in a non accepting state.

(4)If no solution to x i has been found and not all elements of S i have been exam-

ined,then query the oracle B with an unexamined element of S i.

(5)If the machine is in the yes state then halt in an accepting state.

(6)If the machine is in the no state then halt in a non accepting state.

This algorithm will allow for a polynomial time solution on a Non Deterministic Oracle Machine NP B because such a machine will always?nd a solution in step one for any problem in NP if one exists,and halt in step2or3.

However,a Deterministic Oracle Machine may not?nd the solution in step1. When a deterministic machine queries the oracle the oracle only contains one set of the proper cardinality which may or may not be an accepting input set(because the result of the input set is not a requirement for membership in B).The oracle will then place the machine in the yes state if the input set passed to the oracle is equivalent to the one input set of proper cardinality that is an element of B.It is then the case that the Deterministic Oracle Machine may terminate in an accepting

ArXiv,Vol.V,No.N,Month20YY.

6·Jerrald Meek

state when there is no accepting input to the problem.On the other hand if the deterministic oracle machine fails to?nd a solution in step1,and the input set passed to the oracle is not an element of B,then the machine may terminate in a non-accepting state when an accepting input set may exist.It is then clear that oracle B does not produce a reliable polynomial time solution to the problem x i. It is then true that P B=NP B.However this is only because the oracle B is dysfunctional.Oracle B does not actually help a Non Deterministic Oracle Machine to solve a NP problem,because the non deterministic machine has the ability to solve the problem without entering the query state.The oracle is then never queried,and the dysfunctionality of the oracle does not interfere with the operation of the Non Deterministic Oracle Machine.However,a Deterministic Oracle Machine requires the assistance of the oracle to overcome the P=NP Optimization Theorem.It is then the case that a dysfunctional oracle will prevent a Deterministic Oracle Machine from solving a problem in polynomial time while not a?ecting the performance of a Non Deterministic Oracle Machine.

It then becomes easy to see why P A=NP A oracle sets are meager[Mehlhorn 1973].The oracle set must be carefully fabricated in order to create such a condition. If great care has not been taken to ensure that the oracle will be of assistance to a deterministic machine,then the oracle will be dysfunctional.

3.3An Oracle such that NP is not closed under complementation.

A complexity class is closed under complementation if the complements of all prob-lems in that class are members of the same class.Baker,Gill,and Solovay[1975] have shown that there exists an oracle such that one or more problems in NP C have a complement that is not in NP C.

—Let L(X)={x:there exists y∈X such that|y|=|x|}for any oracle X.—Let x be the set of all problems in L(X).

—Let S be the set such that S i is the set of all possible input sets for x i when 1≤i≤|x|.

—Let C(i)represent the elements of C placed in C prior to stage i.

—Let p i(n)<|S i|be a polynomial function of n that represents the maximum number of computations preformed by P X i and NP X i for all oracles X.If p i(n) computations have been preformed,and no accepting element of S i has been found,then the algorithm halts in the non-accepting state without examining all elements of S i.

Create the oracle with the algorithm.

(1)Let i=1.

(2)If NP C(i)

i accepts x i then any one element of S i that is accepted by x i is added

to the set C.

(3)If i<|x|then increment i and continue at step2.

(4)If i=|x|then the oracle set C has been found.

The set C is a set containing exactly one accepting input set for each problem described by L(X)that has an accepting input set.

ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·7 The process of?nding a solution to a problem x i which is in NP with oracle set

C is preformed with the following algorithm.

(1)Pass each element of S i to the oracle and enter the query state.

(2)If the machine is in the yes state for any query,then halt in an accepting state.

(3)If the machine is in the no state for all queries,then halt in a non accepting

state.

For a Non Deterministic Oracle Machine,all elements of S i can be evaluated simultaneously.However,a Deterministic Oracle Machine must iterate threw them one at a time.It is then easy to see that P C=NP C.

To create the oracle setˉC the compliment of C,use the algorithm.

(1)Let i=1.

(2)If NPˉC(i)

rejects x i then add all elements of S i to the setˉC.

i

(3)If i<|x|then increment i and continue at step2.

(4)If i=|x|then the oracle setˉC has been found.

With the oracle setˉC a Deterministic Oracle Machine can solve the compliment of any NP problem by performing one query.This is becauseˉC contains all input sets for any problem in co-NP that has at least one input set that results in the problem evaluating true.If the oracle places the machine in the yes state for any input set then an accepting input set exists for the co-NP problem,although the accepting input set may not be represented by the string queried.If the oracle places the machine in the no state then no accepting input set exists for the co-NP problem.It is then the case that PˉC?co-NP.

However,this situation requires that the oracle sets C andˉC are created non deterministically.It is then the case that the work of solving these problems has been done by the creation of the oracle sets,and this allows the Deterministic Oracle Machine to avoid the limitations of the P=NP Optimization Theorem when solving co-NP problems.

3.4A P=NP oracle such that NP is closed under complementation.

—Let L(X)={x:there exists y∈X such that|y|=|x|}for any oracle X.—Let x be the set of all problems in L(X).

—Let S be the set such that S i is the set of all possible input sets for x i when 1≤i≤|x|.

—Let D(i)represent the elements of D placed in D prior to stage i.

—LetˉD(i)represent the elements ofˉD placed inˉD prior to stage i.

—Let p i(n)<|S i|be a polynomial function of n that represents the maximum number of computations preformed by P X i and NP X i for all oracles X.If p i(n) computations have been preformed,and no accepting element of S i has been found,then the algorithm halts in the non-accepting state without examining all elements of S i.

Construct the oracle sets D andˉD with the algorithm.

(1)Let i=1.

ArXiv,Vol.V,No.N,Month20YY.

8·Jerrald Meek

(2)Let n=1.

(3)If n is even,then let e=1.

(4)If n is even and S n

e /∈ˉD(i)then?nd the pre?x u o

f S n

e

with length|S n

e

|/2.

(5)If n is even and S n

e /∈ˉD(i)and u is an input set for x|u|and NP D(n)

i

rejects

x|u|,then S n

e

∈D.

(6)If n is even and S n

e

/∈ˉD(i)and e<|S n|then increment e and continue at step 4.

(7)If n is even and S n

e

/∈ˉD(i)and e=|S n|then break to step10.

(8)If n is odd and all elements ofˉD(n)have cardinality less than n,and p i(n)<

2(n?1)/2,then add toˉD all strings queried by P D(n)

i for problem x n.If P D(n)

i

rejects x n,then add to D the next element of S n not queried.

(9)If n is odd,then increment i.

(10)If n<|x|,then increment n and continue at step3.

(11)If n=|x|,then the sets D andˉD have been found.

In steps4and5,elements are added to D if their pre?x is rejected.Notice that if f(x)has no input set resulting in a true evaluation,then f(x)∧g(x)has no input set resulting in a true evaluation.It is then the case that in step4and5,elements are only added to D if they represent a problem that has no accepting input set.

In step8,an input set is added to D if P D(n)

i rejects the problem which that

input set belongs to.However,on the?rst iteration,D(n)will be an empty set. An empty oracle set is equivalent to having no oracle,and so the polynomial time algorithm will not check all possible input sets for the?rst problem examined. For the third problem examined,D(n)may contain an input set if it belongs to a problem that always evaluates false.It is then easy to see that step8adds elements to D that may or may not cause a problem to evaluate true.

Because the elements of D do not have any consistent representation,it then follows that the set D will result in a dysfunctional oracle.A deterministic machine requires a functional oracle set to be able to solve all NP problems,but a non deterministic machine does not rely upon the oracle set when solving NP problems. It then follows that P D=NP D.

In step8,the requirement that all elements ofˉD(n)must have cardinality less than n will always evaluate true.The statement p i(n)<2(n?1)/2will evaluate true for the?rst values of n up to some limit.For problems less than this limit,a polyno-mial number of elements will be added toˉD.The elements will be added regardless of weather or not they result in a true evaluation of the co-NP problem associated to them.It is then clear to see that the setˉD will also result in a dysfunctional oracle,and PˉD will not produce reliable results for any co-NP problem.

3.5A P=NP oracle such that P=[NP∩co-NP].

Baker,Gill,and Solovay[1975]construct the oracle set E by adding elements to the oracle set A which was previously constructed such that P A=NP A.The additional elements in E will result in P E=NP E.The trick is to arrange the additional elements such that if a problem is in NP,and the compliment of the problem is also in NP,then both of these problems are solvable in polynomial time by the oracle P E.

ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·9

In the description of creating oracle E ,it is allowed to start with “any oracle A such that P A =NP A .”Here,the oracle A that was previously constructed in this article will be used.However,remember that oracle A did not contain strings representing input sets,but instead partition encoding was used.It will then be the case that the same encoding speci?cation will need to be used for the additional elements of E .

—Let L (X )={x :there exists y ∈X such that |y |=|x |}for any oracle X .—Let x be the set of all problems in L (X ).

—Let S be the set such that S i is the set of all possible input sets for x i when 1≤i ≤|x |.

—Let e (n )be a function such that e (0)=0and e (x )=22e (x ?1)←x >1.

—Let E (0)=A and let E (n )be the set of elements placed in E prior to stage n .—Let r be the set of all possible values for j,k ←j ∈N,k ∈N,j =k .

—Let r j (i )denote the j element of set r i ,and r k (i )denote the k element of r i .—Let p i (n )<|S i |be a polynomial function of n that represents the maximum number of computations preformed by P X i and NP X i for all oracles X .If p i (n )computations have been preformed,and no accepting element of S i has been found,then the algorithm halts in the non-accepting state without examining all elements of S i .

Create the oracle set E with the algorithm.

(1)

Let n =1.(2)

Let i =1.(3)

Let l ∈S n .(4)If e (n ?1)<(log 2|l |)≤e (n )≤max p r j (i )(l ),p r k (i )(l )

neither NP E (n )r j (i )or NP E (n )

r k (i ).accepts x n ,then j,k is unsatis?ed.

(5)If p i (e (n ))≥2e (n ),then i,i is unsatis?ed.

(6)If j,k was not determined unsatis?ed in step 4,and i,i was not determined

unsatis?ed in step 5,then increment i .

(7)If j,k was not determined unsatis?ed in step 4,and i,i was determined

unsatis?ed in step 5,and P E (n )i rejects x n ,then add to E the encoding of x n with the next unevaluated element of S n .

(8)If j,k was not determined unsatis?ed in step 4,and i,i was determined

unsatis?ed in step 5,then increment i .

(9)If i <|N |then increment n and continue at step 3.

(10)If i =|N |then the set E has been found.

Notice that when i,i is unsatis?ed,then P E (n )i will be run on x n .The set E (n )will only contain elements relevant to x n if it was inherited from set A .It is then the case that P E (n )i will only reject x n when x n has no accepting input set.In step 7,if i,i is unsatis?ed,and P E (n )i rejects x n ,then the input set encoding for x n will always be an encoding that represents a partition containing no accepting

input set.It will then be the case that P E will accept x n when a Non Deterministic

ArXiv,Vol.V,No.N,Month 20YY.

10·Jerrald Meek

Oracle Machine would halt in a non accepting state without querying the oracle. Therefore,P E=NP E because the oracle E is dysfunctional when handling some problems.

Letκbe the set of all problems in NP which have complements in NP.When x n∈κ,then j,k will be satis?ed.When j,k is satis?ed then no strings applicable to x n will be added to E.It is then the case that the subset of E that applies to all elements ofκwill be identical to the subset of A that applies to all elements ofκ. So P E=NP E when the problem being evaluated is an element ofκ.

3.6An oracle set such that P F?[NP F∩co-NP F]?NP.

Baker,Gill and Solovay[1975]do not lay out the speci?c method for creating oracle F.However they do provide an outline which includes creating two languages L1(F)and L2(F)such that L(F)=[L1(F)∪L2(F)].Two oracle sets must also be created by two di?erent methods,and F is the union of these two oracle sets. However,notice that if P F?[NP F∩co-NP F],and[NP F∩co-NP F]?NP, then P F?of NP.

It has already been demonstrated that an oracle set can be created such that P A=NP.In other words the set of problems solvable by a Deterministic Oracle Machine with oracle set A in polynomial time is equivalent to the set of problems solvable by a Non Deterministic Turing Machine in polynomial time.

It is then the case that the only new condition of oracle set F is that[NP F∩co-NP F]contains all problems in NP.This is the same thing as saying that NP is strictly contained within co-NP.

Earlier,it was shown that an oracle set C could be created such that NP C is not closed under complementation.The reason that oracle set C allowed this condition was because it resulted in all problems in co-NP being solvable in polynomial time by PˉC,while problems in NP where not solvable in polynomial time by P C.

It is then easy to see that an oracle F could be created such that all problems in NP are solvable in polynomial time by P F,and all problems in co-NP are solvable in polynomial time by PˉF.Under such an oracle the complexity classes NP,and co-NP are both contained by P.

If co-NP?PˉF,and NP?P F,then P F?[NP∩co-NP].All problems in both NP and co-NP have polynomial time solutions on a Deterministic Oracle Machine with oracle set F.It then follows that all problems in NP and co-NP have polynomial time solutions on a Non Deterministic Oracle Machine with oracle set F.

4.ORACLE RELATIVIZATIONS AND P VS.NP SOLUTION METHODS.

Here,the relation of oracle relativizations to the P vs.NP question will be exam-ined by creating an analog of the P vs.NP question.Two complexity classes will be created,PΛand NPΛ;the question will be asked,is PΛ=NPΛ?

To create the analog complexity classes,one problem that is obviously in P will be excluded from PΛ.Any problem in P will due,here the problem used will be the set-sum problem.The set-sum problem will be de?ned as:

—Let S be a set of real numbers.

—Let r be the number of elements in S.

ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·11—Let M be a real number.

r

S i=M

i=1

Given the value of S and M,determine if the equality evaluates true.

Notice that the set-sum problem is similar to the0-1-Knapsack problem,and could be solved by?nding the sum of all subsets of S,but only evaluate true if the one subset of S that contains all elements of S sums to M.In the analog complexity model,it will be assumed that this is the only known method of solving set-sum. An analog complexity model will be created which ignores the existence of some NP problems(such as NP-complete problems).The analog complexity classes will be de?ned as:

—Let NPΛcontain all problems known to be in P assuming P=NP.

—Let PΛcontain all problems in NPΛexcept the set-sum problem.

In the analog computational model NPΛcontains all problems known to be solv-able in non deterministic polynomial time,while PΛcontains all problems known to be solvable in deterministic polynomial time.In the analog question PΛ=NPΛassume that no method has yet been found to prove that set-sum is a member of PΛ,yet set-sum has not been conclusively excluded from PΛ.

Now the following questions may be asked.

—Does there exist an oracle such that P AΛ=NP AΛ?

—Does there exist an oracle such that P BΛ=NP BΛ?

—Does there exist an oracle such that NP CΛis not closed under complementation?—Does there exist an oracle such that P DΛ=NP DΛbut NP DΛis closed under com-plementation?

—Does there exist an oracle such that P FΛ?[NP FΛ∩co-NP FΛ]?NPΛ?

It should be easy to see that the answer to all of these questions is yes.If inconsistent relativizations are an indication of the di?culty of the PΛvs.NPΛproblem,then the problem of proving the set-sum problem solvable in deterministic polynomial time must be at least as di?cult as proving that NP-complete problems are solvable in deterministic polynomial time.

Is the set of computable oracles such that P XΛ=NP XΛmeager?If so,then does that indicate a greater likelihood that PΛ=NPΛ?

With this analog it happens to be the case that PΛ=NPΛ.If the P vs.NP ques-tion is dependant on oracle relativizations,then the analog PΛvs.NPΛquestion should indicate that P=NP.If P vs.NP is dependant on oracle relativizations, then it should be expected that P=NP could be proven by?nding the relation be-tween the polynomial time solvability of set-sum and the relativizations of PΛand NPΛ.If such a relation exists,then it should provide an indication of how to prove P=NP.However,if no such relation exists,then there must exist no dependancy between oracle relativizations and the solution to the P vs.NP question. Obviously,the proof that PΛ=NPΛcan be accomplished by eliminating the evaluation of all subsets of S for the set-sum problem and only evaluating the one

ArXiv,Vol.V,No.N,Month20YY.

12·Jerrald Meek

relevant subset.It is known that the only relevant subset is the subset equivalent to S.This is known because the original de?nition of the problem says it is so.Is there some way that the oracle relativizations also identify the one relevant subset of S?If so then the relativizations should identify a limited partition of relevant subsets for the Knapsack problem.

It is then easy to see that oracle relativizations only tell us that the complexity of any given problem can be hidden by oracle set creation.Essentially,using an oracle to solve a NP-complete problem in deterministic polynomial time is the reverse operation of taking a problem from the P complexity class and pretending that it has no deterministic polynomial time solution.When applied to a NP-complete problem,which may actually have no deterministic polynomial time solution,an oracle such that P A=NP A allows us to pretend that NP-complete problems have deterministic polynomial time solutions.

5.CONCLUSION.

In this article all six oracles form Baker,Gill and Solovay[1975]have been examined. As a result,the following things can be said about the oracles.

—Oracle set A such that P A=NP A is a functional oracle which allows a Deter-ministic Oracle Machine to solve any NP problem with a polynomial number of queries.

—Oracle set B such that P B=NP B is a dysfunctional oracle which fails to allow a Deterministic Oracle Machine to solve all NP B problems with a polynomial number of queries.

—Oracle set C such that NP C is not closed under complementation is a dysfunc-tional oracle such that a Deterministic Oracle Machine can not solve all NP problems with a polynomial number of queries,although a Deterministic Oracle Machine could solve any co-NP problem with one query.

—Oracle set D such that P D=NP D but NP D is closed under complementation is a dysfunctional oracle with a dysfunctional complement.It is then the case that a Deterministic Oracle Machine can not solve any NP problem or any co-NP problem in polynomial time.

—Oracle set E such that P E=NP E and P E=[NP E∩co-NP E]is a dysfunctional oracle that allows a Deterministic Oracle Machine to solve a NP problem in polynomial time when the compliment of the problem is also in NP.

—Oracle set F such that P F?[NP F∩co-NP F]?NP is a functional oracle which allows a Deterministic Oracle Machine to solve all problems in NP and all problems in co-NP in polynomial time.

If P=NP then all problems in NP will be solvable in deterministic polynomial time with or without an oracle set.It would then be the case that a Deterministic Oracle Machine would only be dependant on an oracle set to solve a problem in NP or co-NP if the machine is not using an optimal algorithm.It is possible to create an algorithm for any NP problem such that a solution would require exponential time on a Non Deterministic Turing Machine.This however does not disqualify the problem’s membership in NP.Likewise,just because a NP problem has a determin-ArXiv,Vol.V,No.N,Month20YY.

Independence of P vs.NP in regards to oracle relativizations.·13 istic exponential time solution,this does not disqualify that problem’s membership in P.Therefore,the oracle relativizations are no indicator of P vs.NP.

If P=NP then any problem not ordinarily in P will be solvable in polynomial time by a Deterministic Oracle Machine only when the oracle set is functional for that problem.In this case if P=NP then the Baker,Gill,and Solovay model works exactly as would be expected.

The meagerness of computable P X=NP X oracle sets also seems not to indicate anything about the P vs.NP problem.That is,we should expect a functional oracle for any purpose to be meager.All of these observations lead to the conclusion that the P vs.NP question is independent of oracle relativizations.

6.VERSION HISTORY.

The author wishes to encourage further feedback which may improve,strengthen, or perhaps disprove the content of this article.For that reason the author does not publish the names of any speci?c people who may have suggested,commented,or criticized the article in such a way that resulted in a revision,unless premission has been granted to do so.

arXiv Current Version

20May08Submitted to arXiv.

—Clari?cations were made for some statements.

—The Oracle relativizations and P vs.NP solution methods section was added.—Refrance to[Bennett and Gill,1981]and[Mehlhorn1973]were added.

arXiv Version2

16May08The article was withdrawn due to misleading statements and incomplete research.

arXiv Version1

14May08Submitted to arXiv.

REFERENCES

Baker,T.,Gill,J.,and Solovay,R.1975.Relativizations of the P=?NP question.SIAM J.

Comput.4,(Dec.),431-442.MR395311.Zbl0323.68033.

Bennett,C.,and Gill,J.1981.Relative to a random oracle A,P A=NP A=co-NP A with probability1.SIAM http://m.wendangku.net/doc/ed78300e6c85ec3a87c2c548.htmlput.10,(Feb.),96-113.MR0605606.Zbl0454.68030.

Meek,J.2008.P is a proper subset of NP.arXiv:0804.1079Article1in series of4.

Meek,J.2008.Analysis of the deterministic polynomial time solvability of the0-1-Knapsack problem.arXiv:0805.0517Article2in series of4.

Mehlhorn,K.1973.On the size of sets of computable functions.14th Annual Symp.on Automata and Switching Theory(Univ.Iowa,Iowa City,Iowa),190-196.MR429513.

Received xx/2008;revised xx/2008;accepted xx/2008

ArXiv,Vol.V,No.N,Month20YY.

相关推荐
相关主题
热门推荐