In this final set of comments on
questions received, I'm going to
address some subtleties regarding
decidability and NP-completeness.
My first point is that single
instances of a problem, that is,
one input to a Turing machine,
will always be decidable.
But that decidability is technical.
And it's useless if the underlying
problem is really a hard one.
And I was pleased to see that people are
thinking how they could form a start up
based on their solution to P equals NP.
Here in Silicon Valley we like
to see people thinking that way.
It's not just about
intellectual challenges,
it's about making the world a better
place and getting rich while doing it.
The first question from the form
concerns a doubt about my
comment regarding Rice's theorem that
as a consequence of that theorem,
it is impossible to tell whether a program
does something specific like a sort.
Let's suppose we have a program that is
alleged to sort an input list of intigers.
The questioner suggested that we could
feed the program a list of intigers,
run it, and
see whether the output is sorted.
We could even feed the same program any
finite number of lists like a million.
Lists in turn, it is true that
if the program fails to sort
any of the finite number of input lists,
then you know it is not a sorting program.
However, just because it sorts a million
inputs correctly doesn't mean it
will sort the million and first correctly.
I can give you several examples
of bugs that only showed up in
one out of a million or more cases.
The most famous is probably the Pentium
multiplier bug, with a much
tinier than one in a million odds of it
showing up on any given multiplication.
But, people were getting errors due to
the hardware, rather than the program.
The point is that testing is a good idea.
It does uncover most bugs.
But, that's still not an algorithm for
deciding whether a program does what it
has claimed to do under all circumstances.
And, in fact, there is no such algorithm.
Rice's theorem proves that.
It is worth remembering that problems, or
the languages or questions bout
an infinite number of instances.
Instances.
The answer to all or all but one of those
instances may be no, but a solution to
the problem still has to deal
correctly with all possible instances.
Single instances of a problem
are alway decidable although we can't
necessarily tell what the answer is.
That is, suppose we have a problem
represented by language l and we ask if w,
a single instance is in L.
There are two Turing machines,
one of which answers yes,
that is it accepts any input and
the other of which answers no.
That is it rejects all inputs.
One of these Turing machines
answers the question, is w in L?
Unless L is recursive,
I can't figure out which of the two
Turing machines answers the question.
But I am absolutely certain that one does,
and therefore the question.
Is w in L is decidable?
It has a Turing machine that always
halts and gives you the correct answer.
Of course, this observation is useless,
since we can't really solve anything with
it that we couldn't already solve
because the language L was recursive.
The second question I would like to
address is almost the same question, but
regarding intractability,
rather than decidability.
The question or
hypothesis that they could invent an
algorithm that runs in polynomial time and
appears to run some NP-complete problem,
let's say SAT to be concrete.
That is, they tested it on
a million expressions and
it gave the correct answer in all cases.
They then asked whether they could
sell the solution to a company.
The objective would be that the company
would be able to solve problems quickly
that no one else would be able to
solve in less than exponential time,
and thus could charge for the service.
That's not quite the right approach.
The right thing to do would be
to start a company of your own.
Implement the solution and
sell the service.
Once you have a business going,
your company would be much more valuable
than an unimplemented and untested idea.
So you could sell the company for
much more than you could sell the idea.
You may, for example,
have heard how Sergey Brin and
Larry Page offered to sell the key ideas
behind Google to Yahoo for $1 million.
But Yahoo wasn't interested
in developing the idea.
Now Google is worth ten
times what Yahoo is worth.
The second issue is whether you
can could the algorithm secret and
still convince people that you had
a solution to an NP-complete problem.
And therefore all NP-complete problems.
That's not impossible.
And we'll talk about it on the next slide.
There's a fairly ancient theory called
zero-knowledge proofs due to Goldwasser,
Micali, and Rackoff.
Their techniques were motivated
by exactly this conundrum.
If you had solved p equals NP in
the positive and you wanted to prove to
people that you had a solution without
revealing your algorithm, could you do it?
In the previous problem session we argued
that proofs of theorems require a social
process where you reveal your proof
to interested mathematicians, and
they can examine and
argue about anything that seems doubtful.
Well, the methodologically behind zero
knowledge proofs is also a social
process but of a very different kind.
The verifier gives you many instances
of the problem you want to solve.
And you produce a solution to each,
but do not reveal them.
You are then asked the question
about each solution and
must answer them all
correctly to be believed.
There's considerably more to the concept,
however.
Wikipedia has a good explanation of
how a Zero-Knowledge proof works.
If you had a solution to
the NP complete problem.
Called Hamilton Cycle that is
whether a graph has a cycle that
contains all the nodes exactly once.
We just talked about being able to solve
single instance of undecidable problems.
The same idea applies to
attractable problems as well.
That is, suppose we have an empty,
complete problem or language L, and
we want to know in polynomial time
whether a given instance, w is in L.
Since everything is now decidable,
we can even run
the non-deterministic polytime touring
machine and see whether W is an L.
It will take us exponential time,
but eventually we finish.
And now we can design our polynomial
time Turing machine to take input w and
accept or reject whichever our exponential
time analysis told was correct.
This Turing machine can do anything
it likes on inputs other than w.
But as was the case for
undecidable problems this
approach doesn't really help.
We can precompute the solution to
any finite number of instances and
use them in a polytime Turing machine.
But that is not the same
as solving the problem.
Out quote solution is still useless for
any instance whose solution
we did not precompute.
But let us return to
the original question.
Suppose someone came up with
a polynomial time algorithm that they
thought might solve.
Sat.
But they couldn't prove it.
Could they test it on say,
one million expressions and
check that it worked well on all million?
If so, wouldn't that be good evidence that
the algorithm worked for any expression?
Well, we have to be a little careful
how the test expressions are selected.
So the easy case is if there were
a satisfying assignment that is,
the answer is yes.
In this case, we could expect
the algorithm to provide at least one
example of a satisfying assignment which
we could check easily and quickly.
The hard case is when your
algorithm says no there is no.
There is no way known to
verify that no is the right
answer without checking the exponential
number of possible truth assignments.
That's not feasible for a million test
cases, or even one large test case.
But perhaps we could handle this case
if we knew that any expression that
had a satisfying assignment
had many of such assignments.
If that were the case,
a randomized test would work.
Pick a reasonable number of assignments
and evaluate the expression on each.
If any of them are satisfying
then your algorithm is wrong but
if none are satisfying then you could
conclude with high probability that your
algorithm gave the correct no answer.
Unfortunately, there are lots of
expressions that have exactly one
satisfying assignment.
For example, consider what happens if you
apply the construction in Cook's theorem,
to a deterministic Turing machine.
There will be only one truth assignment,
the one that reflects the unique
computation of that Turing machine.
I have enjoyed greatly the experience
of using modern technology to
present this material on the basis of
automata theory to a worldwide class.
Thanks to all of you who stuck with
the difficult and challenging material.
I hope it will have some good effect
on your future careers even if
you aren't the one to
prove that p equals NP.
And I hope everyone who has come this
far will do well on the final exam.
As mentioned on the class announcements,
the cla, exam will be available for
the three hour period of your choice,
during the week starting 11th of June.
Certificates of accomplishment
will be emailed to all
whose total mark on the class are.
To at least 50% with the final
accounting for half the marks and
the homework's accounting
to the other half.
Good bye and good luck.