How to prove NP=P

How to Prove NP = P

Pick your favorite NP-Complete problem.
I have been working with 3SAT lately.

Be specific about what you are trying to prove.

I want to show NP = P.

I will work with the set of solvable 3SAT instances.
I can ignore unsolvable 3SAT instances
because unsatisfiability is not known to be in NP.

Definitions matter.
Define as many things as you can.
Here are some examples of why.

The Satisfiability problem is often defined as a
decision problem. Does there exist an algorithm
that returns true if and only if the input 3SAT
instance is satisfiable?

Algorithm is usually defined as a Turing machine (TM).

It is simple to prove NP=P using these definitions.
All I need is a Turing machine that immediately halts
and returns true. We already know all the 3SAT
instances in our set are satisfiable by definition.

A more convincing definition would be to require
the TM to return a certificate of satisfiability.
A satisfying assignment of variables (possibly
a partial assignment) would qualify as a certificate
of satisfiability.

Even with this definition it is still simple to prove NP=P.

For any finite set of satisfiable 3SAT instances there
exists a TM that returns a satisfying assignment in
a polynomial number of steps.

Proof:
Assume I use other means to find a satisfying
assignment for each 3SAT instance in the set.
I take this table of certificates and embed it
into a TM. The TM reads the input number,
looks up that position in the table and
returns the appropriate satisfying assignment.

You might notice my proof says nothing about
the size of the table of satisfying assignments
and I am assuming I can look something up in a table
in polynomial time. This might not be a good
assumption if the table is quite large.

Despite these objections, this can be made into
a valid proof. For any finite set of satisfiable
3SAT instances there exists a TM that will return
a satisfying assignment in polynomial time.

The "look it up in a table" argument is handy to know.
It applies anytime we put some condition on the
size of the input to the TM like the input set is finite
or the set of 3SAT instances with 10 variables, etc.

Now for a better definition of what I need to prove.

Does there exist a TM such that, given an arbitrary
satisfiable 3SAT instance, the TM returns a
satisfying assignment using a polynomial number of steps?
Polynomial means with respect to the size of the input.

I have to add that the method for converting the
3SAT instance into an input tape has to be relatively
efficient. Artificially making the input bigger is
cheating. Godel numbering won't cut it.

I have been looking at "guessing" solvers. A
guessing solver simply guesses an assignment
of variables and then checks if the assignment
satisfies the 3SAT instance.

If I can show there exists a guessing solver
that makes at most a polynomial number of bad
guesses before finding a satisfying assignment
then I can prove NP=P.

If one wanted to prove NP =/= P, I think
showing no guessing solver can find a
satisfying assignment for every satisfiable
instance in polynomial guesses would come
very close to proving NP =/= P.

It has been proven that a solver which randomly
guesses assignments can solve most satisfiable
3SAT instances in polynomial time. This is
because most 3SAT instances are easy to solve.

This won't help me prove NP=P, but it does have
practical consequences. Even though there are
300 variable test instances that can't be solved
in a reasonable amount of time by modern solvers,
there are real world optimization problems with
thousands of variables that can be and have been
solved by modern solvers.

One of the advantages of looking at guessing
solvers is that many other types of solvers
can be modeled as guessing solvers.

Davis Putnam Longman Loveland (DPLL) is a method
used by many modern SAT solvers. DPLL extends a
partial assignment of variables until it finds
a satisfying assignment or some clause can't be
satisfied with the current assignment. DPLL
backtracks and tries a new assignment if it
doesn't find a satisfying assignment.

I can equate backtracking with making a bad guess.
This means DPLL and most other backtracking solvers
can be modeled as guessing solvers.

If I can show there exists a backtracking solver
which backtracks at most a polynomial number of
times before finding a satisfying assignment,
I can prove NP=P.

There are numerous backtracking schemes for DPLL.
Even though these methods have been extensively
studied, little is known about their complexity.

I have been trying to "fine tune" some metrics
for measuring the behavior of backtracking schemes.

I have been studying clause based solvers lately
and have found some clause based metrics.

Assume I order the clauses from highest order
to lowest order. For every bad guess there is
at least one clause that can't be satisfied.
Therefore there is a highest order clause
that can't be satisfied.

Assume I keep track for each clause of how
often that clause is the highest order
unsatisfied clause (HOUC).

I can prove NP=P if I can show no clause
will be the HOUC more than a polynomial
number of times.

This suggests a guessing solver might want
to identify clauses with large HOUC and
try to guarantee these clauses get satisfied.

Soon, I plan to post a clause based solver
with a backtracking scheme that is easily
quantifiable. I show this backtracking scheme
can be reduced to a set of DNF expressions.
The number of times the solver will backtrack
is related to the number of minterms in these
DNF expressions.

Needless to say, I am having trouble proving
the number of minterms in any of the DNF
expressions is at most polynomial. I can show
that very high order clauses and very low order
clauses can't be the HOUC more than a polynomial
number of times.

Russell
- 2 many 2 count

reasterly@gmail.com wrote:
> How to Prove NP = P

This should have been called `How not to prove P = NP:'

> I will work with the set of solvable 3SAT instances.
> I can ignore unsolvable 3SAT instances
> because unsatisfiability is not known to be in NP.

.... No.

This is the definition of 3SAT:
Given a conjunction of Horn clauses with 3 elements, does there exist an
assignment of variables satisfying the expression?

You have to say it is either satisfiable or not; you must give correct
answers if the expression is satisfiable or not.

> The Satisfiability problem is often defined as a
> decision problem. Does there exist an algorithm
> that returns true if and only if the input 3SAT
> instance is satisfiable?

It is not `often defined' as a decision problem. It is a decision problem.

> It is simple to prove NP=P using these definitions.
> All I need is a Turing machine that immediately halts
> and returns true. We already know all the 3SAT
> instances in our set are satisfiable by definition.

No you don't. Your goal is to show that the expression is either
satisfiable or not, a YES or NO answer. Any boolean expression
consisting of a disjunction of Horn clauses with 3 elements per clause
is acceptable input.

> For any finite set of satisfiable 3SAT instances there
> exists a TM that returns a satisfying assignment in
> a polynomial number of steps.

Turns out that there are an infinite number of 3SAT instances. A -> B
may be true, but if A is false, you don't know one whit about B.

On Nov 11, 4:56 pm, Joshua Cranmer <Pidgeo...@gmail.com> wrote:
> reaste...@gmail.com wrote:
> > How to Prove NP = P
>
> This should have been called `How not to prove P = NP:'
>
> > I will work with the set of solvable 3SAT instances.
> > I can ignore unsolvable 3SAT instances
> > because unsatisfiability is not known to be in NP.
>
> ... No.
>
> This is the definition of 3SAT:
> Given a conjunction of Horn clauses with 3 elements, does there exist an
> assignment of variables satisfying the expression?
>
> You have to say it is either satisfiable or not; you must give correct
> answers if the expression is satisfiable or not.
>
> > The Satisfiability problem is often defined as a
> > decision problem. Does there exist an algorithm
> > that returns true if and only if the input 3SAT
> > instance is satisfiable?
>
> It is not `often defined' as a decision problem. It is a decision problem..
>
> > It is simple to prove NP=P using these definitions.
> > All I need is a Turing machine that immediately halts
> > and returns true. We already know all the 3SAT
> > instances in our set are satisfiable by definition.
>
> No you don't. Your goal is to show that the expression is either
> satisfiable or not, a YES or NO answer. Any boolean expression
> consisting of a disjunction of Horn clauses with 3 elements per clause
> is acceptable input.

Like I said, definitions are important.
I was careful to point out that I wasn't including unsolvable 3SAT
instances.
There are defintions of NP that include UNSAT, but mine doesn't.
I also explained why I didn't frame NP as a decision problem.
Instead, I require the algorithm to return a certificate
of satisfiability.

I define a problem to be in NP if, given a certificate of
satisfiability
for a particular instance of the problem,
it is possible to prove the instance is satisfied by the
certificate in a polynomial number of steps.

There is no known "certificate of unsatisfiability".
I don't include unsatisfiability in NP.

This may not be the standard definition.
I am not positive there is a standard definition.
That is why I think it is important to define what one
means when talking about NP ? P .

Russell
- 2 many 2 count

reasterly@gmail.com wrote:
....
> Like I said, definitions are important.
> I was careful to point out that I wasn't including unsolvable 3SAT
> instances.
> There are defintions of NP that include UNSAT, but mine doesn't.
> I also explained why I didn't frame NP as a decision problem.
> Instead, I require the algorithm to return a certificate
> of satisfiability.
....

If you are going to make up your own definitions, rather than use
conventional ones, it would be a *very* good idea to think up your own
names for the newly defined entities.

Talking about "NP=P" makes people think you are talking about the famous
problem involving the complexity classes usually called "P" and "NP".
That is bound to cause confusion if you are really talking about a new
problem you are constructing, using your own definitions.

Patricia

reasterly@gmail.com wrote:
> There are defintions of NP that include UNSAT, but mine doesn't.
> I also explained why I didn't frame NP as a decision problem.
> Instead, I require the algorithm to return a certificate
> of satisfiability.

The complexity classes P and NP are defined to be decision problems. If
you don't define them as such, you're going to be speaking essentially
gibberish to most people.

Here's a clear example of the fallacy:
Let R be the set of rationals. The set of rationals is countable (since
rational numbers is a Cartesian product of two countable sets). R is
therefore countable; since R is the set of real numbers, the real
numbers are countable.

> This may not be the standard definition.
> I am not positive there is a standard definition.
> That is why I think it is important to define what one
> means when talking about NP ? P .

How about this definition?
<http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf>

This is the definition that Clay Mathematics Institute uses as the basis
for the Millennium Prize problems, i.e. proving this version will net
you $1M.

On Nov 11, 6:08 pm, Joshua Cranmer <Pidgeo...@gmail.com> wrote:
> reaste...@gmail.com wrote:
> > There are defintions of NP that include UNSAT, but mine doesn't.
> > I also explained why I didn't frame NP as a decision problem.
> > Instead, I require the algorithm to return a certificate
> > of satisfiability.
>
> The complexity classes P and NP are defined to be decision problems. If
> you don't define them as such, you're going to be speaking essentially
> gibberish to most people.
>
> Here's a clear example of the fallacy:
> Let R be the set of rationals. The set of rationals is countable (since
> rational numbers is a Cartesian product of two countable sets). R is
> therefore countable; since R is the set of real numbers, the real
> numbers are countable.
>
> > This may not be the standard definition.
> > I am not positive there is a standard definition.
> > That is why I think it is important to define what one
> > means when talking about NP ? P .
>
> How about this definition?
> <http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf>
>
> This is the definition that Clay Mathematics Institute uses as the basis
> for the Millennium Prize problems, i.e. proving this version will net
> you $1M.

I will be happy if I prove my version.

How to prove NP=P - Theory

How to prove NP=P

LinkBack

Thread Tools

How to prove NP=P

Re: How to prove NP=P

Re: How to prove NP=P

Re: How to prove NP=P

Re: How to prove NP=P

Re: How to prove NP=P