Universal Turing Machine with Active Graph
Departure from the Theology
Excerpt from
theory-edge and algorithm-forge
Baba Laboratory
Michiro Nasu
Af.1230: 2001-12-18 03:37:30 +0900 Polynomial Reduction from AGTM to SAT
Te.4597: 2001-12-16 12:55:14 +0900 Greeting to the Moderator
Te.4593: 2001-12-15 15:38:12 +0900 Official Apology
Af.1182: 2001-12-11 13:03:08 +0900 Generalized Active Graph Machine
Af.1142: 2001-12-08 09:36:27 +0900 Paradox on emulating the emulator itself
Af.1107: 2001-12-07 00:03:40 +0900 Active Graph Machine
Af.0922: 2001-11-24 08:11:39 +0900 Holy Cow
Te.4282: 2001-11-04 15:40:59 +0900 Polynomial Time Reduction
Te.4279: 2001-11-04 02:59:38 +0900 Correction and Supplement
Te.4277: 2001-11-03 05:55:34 +0900 Departure from the Theology
See also "After Math" paragraph, bottom line of HCP to SAT Conversion Cubic Time Algorithm. MN (2006-09-29)
-------- Original Message No.1230
--------
Subject: [algorithm-forge] Re: Active Graph Machine
Date: Tue, 18 Dec 2001 03:37:30 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Re: Departure from the Theology
Hi Lasse and all!
I'm very happy that I've got a polynomial transformation from AGM
to SAT. thanks for your help and advises. this is my offering to
you in return.
we changed GAGM again to a bit more general formulation such that
it has arbitrary size of alphabet and the head moves +1, 0 and -1.
hence it can emulate any 1-tape TMs now. we'll call this new version
AGTM. nodes [of graphs read] in AGTM are tuples <time, position, state, symbol> and
arcs are <time, node1, node2, symbol>.
ACTIVE GRAPH TURING MACHINE (AGTM):
INPUT:
1)Integers L, M, N, p_0≤M, q_0/q_Y≤N, b≤L.
2)Labeled directed multi-graph G(V,E).
Each vertex v is labeled with an element of {M*M*N*L},
which we denote by <t,x,y,z>. Each directed edge e is labeled
with an element of {M*V*V*L}, which we denote <t,v,v′,z>.
For an ordered vertex pair (v,v′) such as v=<t,x,y,z>
and v′=<t+1,x′,y′,z′>, if x′=x-1,x or x+1,
then it has at most L multi-edges <t,v,v′,> from v to v′.
3)Integer array T[M] and word w ∈ {0,...,L}^M of length |w|≤M.
w is placed in T[M] from p_0 and the rest of T[] is filled with b.
QUESTION: Is there a time sequence of ID transitions starting at the
initial ID and terminates at a final ID in at most M steps, where
• ID is a tuple <t,X,Q,S> such that time t≤M, X≤M, Q≤N and S is a
subset of vertices <t,j,Q,l> ∈ V as T[j]=l at time t for all j≤M,
• Initial ID is an ID <1,p_0,q_0,S0>, and S0 is a subset of vertices
<1,j,q_0,l> such that T[j]=l at time t=1 for all j≤M, and
• Final ID is an ID with Q=q_Y.
REMARK: An ID transition <t,X,Q,S>→<t+1,X',Q',S'> is defined as:
If there is an edge <t,v,v',z"> such as v=<t,X,Q,z>,
v′=<t+1,x′,y′,z′>, T[X]=z and T[x′]=z′ at time t,
Then set T[X]=z", X′=x′ and Q′=y′, and
make vertex subset S′ of vertices <t+1,j,Q',l>
such as T[j]=l for all j≤M.
Else reject.
POLYNOMIAL REDUCTION [AGTM]→[SAT]:
INPUT:
1) Integers L, M, N, p_0≤M, q_0/q_Y≤N, b≤L.
2) Directed multi-graph G(V,E).
V={<t,x,y,z>}, t≤M,x≤M,y≤N,z≤L.
E={<t,v,v′,z>}, t≤M, v,v′∈V and z≤L.
3) Integer array T[M] and word w∈{0,...,L}^M of length |w|≤M.
OUTPUT: A boolean expression F = F1*F2*F3*F4*F5*F6*F7.
Variables: label value
• nodes : v<t,x,y,z>, t≤M, x≤M, y≤N, z≤L.
• arcs : e<t,v1,v2,z>, t≤M, v1,v2∈nodes, z≤L.
• states : Q<t,q>, t≤M, q≤N.
• head pos : H<t,x>, t≤M, x≤M.
We make a boolean expression representing, for each ID(t) at time
t=1 to M, that every node-variables in ID(t) are TRUE and every
transition arc-variables are TRUE. WOLOG we assume that every
vertex has an edge to <t+1,x,q_Y,z>.
F1.FOR all v=<t,x,y,z>, 1<t≤M, x≤M, y≤N, z≤L:
//for all nodes at time t>1
IF Q<t,y>=TRUE THEN //current state is y
FOR all q≤N: //for all previous state
IF Q<t-1,q>=TRUE //previous state was q and
IF H<t-1,x>=FALSE AND //previous head was not at x
v1<t-1,x,q,z>=TRUE //node v1 is in ID(t-1)
THEN v<t,x,y,z>=TRUE //the node v is in ID(t)
ELSE FOR all z1≤L //node v1 is in ID(t-1)?
IF v1<t-1,x,q,z1>=TRUE AND
e<t-1,v1,v,z>=TRUE //there exists an arc from v1
THEN //to v with write symbol z
v<t,x,y,z>=TRUE //the node v is in ID(t)
OTHERWISE v<t,x,y,z>=FALSE //the node v is not in ID(t)
F2.FOR all 1≤t<M, z≤L: //check inactive edges
FOR all v1<t,x,y,z>, v2<t+1,x′,y′,z′>:
IF v1=FALSE OR v2=FALSE //node v1/v2 is not in ID
THEN e(t,v1,v2,z)=FALSE //edge e is inactive
Note: "IF p THEN q ELSE r" statement can be translated into a
boolean formula ((p AND q) OR (¬p AND r)).
F3.There exists exactly one valid Q<t,q> at time t, for all t≤M.
F4.There exists exactly one valid H<t,x> at time t, for all t≤M.
F5.There exists exactly one valid e<t,v1,v2,z> at time t, for all t<M.
Note: For F3, F4 and F5, we can use a predicate U(x1,x2,...,x(r))
such as U is TRUE iff exactly one argument is TRUE as below.
U(x1,x2,…,x(r))=(x1+x2+…+x(r))*\PRODUCT(¬x(I)+ ¬x(j))[for all I≠j].
F6.Initial ID: H<1,p_0>=TRUE AND Q<1,q_0>=TRUE AND
FOR I=1 to M: v<1,I,q_0,T[I]>=TRUE.
F7.Final ID: Q<M,q_Y>=TRUE.
ANALYSIS: AGTM accepts a word x iff there is a time sequence Π of
accepting ID transitions. it is easy to see that Π is certified in
deterministic polynomial time. hence AGTM is in NP. by the
specification of GAGM [Generalized Active Graph Machine], it can emulate all of 1-tape Turing Machines.
we know that every NDTM can be emulated by some 1-tape TM, thus GAGM
emulates all of NDTM and then is NP-complete.
|V|=M^2*N*L, |E|≤M*|V|^2*L=M^5*N^2*L^3, |T|=M. the size of integers
are at most Max(L,M,N). since L and N are constant for a NDTM M, we
may assume that eventually M is only one variable factor in input
word x for AGTM. hence the length of an element of x is O(logM) and
the length of x is O(M^5*logM). apparently time complexity of the
transducer from AGTM to SAT is polynomial for M and SAT accepts F iff
AGTM accpets x. consequently AGTM is polynomially reducible to SAT
and SAT is definitely NP-complete. it can be said that an input for
AGTM is a program and the multi-digraph D is a programming language.
EOA.
it was so long travel for me, but barely finished.
thanks for all, and be merry X′mas to you!
peace, M.N.
-------- Original Message No.4597
--------
Subject: [theory-edge] Re: Departure from the Theology
Date: Sun, 16 Dec 2001 12:55:14 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Re: Departure from the Theology
hi vlad!
you wrote,
> maybe your letter makes my month.
sorry! but if you read it just as a reading, perhaps not so bad...
> thank you for your apology. in 3.5 years of running
> this list, I have very rarely seen apologies
> from those who are corrected even though it is
> a regular event, esp given the very sharp ppl here.
I'm accustomed to apologize at any time for I always mistake.
(I'm a purpose-built machine for producing errors... )
> as they say in the US, it takes a "big man" to admit
> he is wrong.
I'm not big at all but may never come to be smaller than I am
(by apologizing as I'm the smallest. contrasting, a big man may
become smaller but still big enough...)
> however, I want to reiterate to all here,
> there is no faux paux in being mistaken here about
> any part of science/theory/math, or having a dialogue stemming
> from misconceptions. quite to the contrary, it is part
> of the reason I founded the list, I.e. education, and has consistently
> led to the best threads on the list-- sometimes experts
> are drawn into the deceptively simple questions of neophytes..
simple questions are at most profound.
> the error is in any haughty attitude or disrespect toward
> (a) others on the list (b) my opinion about signal vs
> noise on the list or esp (c) the great scientists
> & their achievements whom we can *all* learn from. if in 3 days,
> some new "numbskull neophyte" shows up with a proof
> that P==NP, it would not bother me, but if he
> made any of those "real" errors, that would be a problem.
OK. I'll be careful of your opinion.
> on the other hand, I must admit tormenting the haughty
> newbies can lead to its own set of pleasures, hahaha
you may have your own pleasures.
> I followed your epic dialogue over on algorithm-forge
> & note lasse was especially helpful & patient. I would
> have liked to have contributed, but the iron bars &
> straightjacket are still in place, wink.. anyway
thanks. but fortunately you are not captured in a cage.
> all your msgs are in the archives for any future
> "neophytes" to learn from. in fact if you posted a summary
> for any future neophytes, surely it would be very useful.
I think that I had a hidden/strong hypothesis like "word is no
stronger than existence". it was upset at least in the domain
of NP (that is the world where we live). now it is almost
unbelievable that I could read books in such a way.
> in science, one leverages the abstract against the
> empirical and vice versa. but there is another leverage
> that goes on, that can be witnessed-- the experts vs the
> newbies and vice versa. the newbies learn respect &
> the experts learn how to most effectively instill it.
having no prejudice is the most significant. but we need some
hypothesis to begin with. it's the problem...
> so, it seems remarkable, but it seems to me,
> humility in science is not really optional. and its
> necessity is not necessarily related to other scientists.
> scientific progress itself/alone requires humility.
the queen demands humility and fidelity of her knights.
M.N.
-------- Original Message No.4593
--------
Subject: [theory-edge] Re: Departure from the Theology
Date: Sat, 15 Dec 2001 15:38:12 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Re: Departure from the Theology
Dear Vlad and all!
I've insisted long that Cook's theorem and those proofs of it were
wrong and invalid. Here I retract all my statements regarding the
issue and express my sincere apologies to all. I admit I was entirely
wrong. It was caused just by my terrible ignorance and misunderstanding
with prejudice for SAT or propositional logic. I greatly appreciate
all of those who patiently kept hearing my selfish arguments and
kindly helped me to understand it by myself.
After closing the thread "Departure from the Theology" here, we
continued the discussion at Algorithm-Forge. At last I constructed
a NDTM called AGM (Active Graph Machine) [1] and proved its NP-
completeness by generic transformation. AGM can emulate all of NDTMs.
So if AGM is reducible to SAT, then SAT is NP-complete and Cook's
theorem holds. Finally I understood that it is able in similar way of
those proofs' techniques. I might be thinking that propositional
calculus is not always almighty. But indeed it is and now I believe
"In the beginning the Word already existed".
Merry X'mas to you and all!
Michiro Nasu a.w.k.a. numskull neophyte
nasukun@...
[1] http://groups.yahoo.com/group/algorithm-forge/message/1107
-------- Original Message No.1182
--------
Subject: [algorithm-forge] Re:Active Graph Machine
Date: Tue, 11 Dec 2001 13:03:08 +0900
From: "Michiro Nasu"
To: algorithm-forge@yahoogroups.com
Re:Active Graph Machine
Hi Lasse and all!
You wrote,
> Oh, I'm afraid that is all the time that I can spend on this right
> now. Anyway, are we agreed that the definition I give above captures
> the idea of your problem, and that the described problem is
> NP-complete? I am sure I can give you a reduction of this problem to
> SAT; not surprisingly, it will be in the same spirit as the proof of
> Cook's theorem, but maybe more direct.
I appreciate your expensive devotion. I pose here a little modified
version of your proposal. I believe this is the most simple and clear
problem/language definition we can offer. The GAGM emulates any finite
single-tape machine with alphabet {0,1} (the simplest NDTM model).
The digraph D is still a multi-graph, but directed multi-edges in D are
at most two for an ordered pair of vertices. It has no longer special
vertices p0, pY and pN. each pair of vertices with value {0,1} is at a
crossing point of a grid board of MxN. Although you proposed random
access movement, I stayed within the range of ordinary NDTM definition
with restricted head movement of +/-1.
I hope you agree to the following and admit it as our progress.
GENERALIZED ACTIVE GRAPH MACHINE (GAGM):
INPUT:
1) Integers M "tape length",
N "number of states",
p_0≤M "initial
head position" and q_0/q_Y≤N
"initial/accept state".
2) A labeled directed multi-graph G(V,E).
Each vertex v is labeled
with an element of {1,...,M}x{1,...,N}x{0,1}, which we denote by
(P[v],Q[v],A[v]).
Each directed edge e is labeled with an element of
{0,1}, which we denote B[e]. For a vertex v, there are at most 4*N
directed edges e(v,v′) where P[v′]=P[v]+1≤M or P[v′]=P[v]-1>0.
3) A word T ∈ {0,1}^M of length |T|≤M.
QUESTION: Is there a vertex v_Y and T′∈{0,1}^M of a final
configuration which can be reached in M computation steps started
at a vertex v_0 of the initial configuration with word T, where
• Configuration at time t≤M is an element of {MxNx(MxNx{0,1})x{0,1}^M),
which we shall denote by (t,q(t),v(t),T(t)), where v(t)∈V,
q(t)=Q[v(t)]≤N, T(t)∈{0,1}^M and T(t)[P[v(t)]]=A[v(t)],
• Initial configuration (0,q_0,v_0,T) at P[v_0]=p_0 and Q[v_0]=q_0,
• Final configuration (n,q_Y,v_Y,T′) at v_Y ∈V and Q[v_Y]=q_Y.
REMARK: A computation step is defined as follows:
Configuration (t,q(t),v(t),T(t)) → (t′,q(t′),v(t′),T(t′)), where
t'=t+1, T(t)[P[v(t)]]=A[v(t)], T(t)[P[v(t')]]=A[v(t')]), and
T(t) and T(t') agree except possibly at the P[v(t)]-th position.
If there is an edge e from v(t) to v(t') such that
q(t)=Q[v(t)], q(t')=Q[v(t')], and B[e]=T(t')[P[v(t)]].
Else reject.
Alright, what does all that mean? The words T(t) in the configuration,
elements of {0,1}^M correspond to the tape of a nondeterministic
Turing Machine which does not use more than M cells. The input word T
is the starting word. The label (P[v],Q[v],A[v]) of a vertex v stands for
"Tape at position P[v] contains the value A[v] when the state is Q[v]".
We should think that, for every state q(t) of the Turing Machine, we
have one vertex v(t) of each possible label, meaning "Tape head in state
q=Q[v] rests on cell P[v], which contains the value A[v]". A transition
just means that we move to a neighboring cell, I.e., a cell at P[v]+/-1
position, changing the value in cell P[v] to the value that is specified
by B[e] of the edge, and the state q from Q[v(t)] to Q[v(t+1)].
Now I think we have done. This is my formal proposal to all.
"Please give us your deterministic polynomial time transformation
algorithm from GAGM to SAT". Thanks again, Lasse!
Regards,
Michiro Nasu
-------- Original Message No.1142
--------
Subject: [algorithm-forge] Active Graph Machine
Date: Sat, 8 Dec 2001 09:36:27 +0900
From: "Michiro Nasu"
To: algorithm-forge@yahoogroups.com
Active Graph Machine
Hi Charlie!
I wrote,
> I invented a machine called AGM (Active Graph Machine) [1].
> it solves all of NP problems L emulating the machine M for L.
> it takes as its input, (1)input word w for the NDTM M, (2)digraph D
> representing the machine specification of M. it outputs an active
> directed path Pi of D representing the accepting computation path
> of M. it is sure that Pi can be verified in polynomial time.
> hence AGM is in NP and thus NP-complete.
here you need not necessarily understand the detail of the description
of machine AGM. you can take AGM just literally as a problem/language
as described with INPUT and PROBLEM.
ACTIVE GRAPH MACHINE PROBLEM (AGM)
INPUT : A word w for NDTM M and a digraph D representing the machine
description of M.
PROBLEM: Find an active directed path Π in D representing an
accepting computation path of M for w.
so, w -> [transducer T for M] -> (w'+D) -> [AGM] -> Π.
(the difference between w and w' is just polynomial and negligible.)
> here is a question to you.
>
> Question: can AGM machine Ma solve AGM problem itself?
> if it is able, what is the answer(solution)?
suppose AGM solves AGM problem itself. what's the input to AGM?
my input word:=my input word w + my machine description D.
it is easy to get D for AGM in polynomial time. however my input
word w is defined recursively! so it turns out like
my input word:=my input word + D
:=(my input word + D) + D
:=((my input word + D)+ D) + D
:=(((my input word + D)+ D)+ D) + D
:
:
a NP-complete problem is a problem such that any NP problems are
reducible to it. it of course includes the problem itself. and it
is believed that any reduction R is reflective, I.e., problem A is
R-reducible to A itself.
I think the above is seemingly relevant to G"odel's first theorem.
you said there is no completeness in a consistent system but we
are talking about "completeness" of a time complexity class.
what do you think about those?
AGM is an emulator of other languages. "when an emulator tries to
emulate itself, what happens?" this is my question.
Michiro
-------- Original Message No.1107
--------
Subject: [theory-edge] Active Graph Machine
Date: Fri, 7 Dec 2001 00:03:40 +0900
From: "Michiro Nasu"
To: algorithm-forge@yahoogroups.com
Active Graph Machine
Dear Mighty Jeditribble!
Here is a machine called AGM (Active Graph Machine). This machine
solves all of NP problems as it is really NP-complete! Can you
show me a deterministic polynomial time algorithm to transform AGM
to SAT? If you succeed it, then I'm willing to take my hat off to
you and formally recognize that SAT is surely NP-complete.
A multi-graph is a graph having multi-edges connecting a pair of
vertices. As for a directed edge e(p,q), we call vertex p outvertex
and q invertex. We say edge e is outgoing from p and incoming to q.
A Turing machine M is composed of the following three parts.
1)A finite set Tau tape symbols, Sigma input symbols, and blank b.
2)A finite set Qs of states including distinguished q0,qY and qN.
3)A finite transition set Delta:{d|(Qs-{qY,qN})*Tau->Qs*Tau*{-1,+1}}.
Active Graph Machine Problem (AGM)
INPUT: A word w of language L ∈ NP and directed multi-graph D(V,E)
representing the specification of single-tape NDTM M for L with time
complexity function F(n)=n^k. Each vertex v ∈ V has property
(tape-index x, symbol y). D has three distinguished vertices p0,pY
and pN lacking property (x,y). Each directed edge e ∈ E represents
a transition d ∈ Delta and has property (state s0, s1, symbol s).
|V|<=(n^k*2+1)*|Tau|+3 and |E|<(|V|*|Qs|*|Tau|+|Tau|+2*|V|)*|Qs|.
PROBLEM: Is there an active directed path Π in D from p0 to pY?
AGM is a multi-tape NDTM and receives input word w of single-tape
NDTM M and the specification of M as an attributed directed multi-
graph D on the input tape. It provides tape-symbol array T[2*n^k+1]
with indices -n^k,...-1,0,1,2,...,n^k and machine state Q. T is
initialized by w on the input tape from T[1] to T[n] and all other
cells are cleared by blank symbol b. The initial state of Q is q0.
A vertex v(x,y) in D is said to be active if T[x]=y. A directed edge
e connects vertex v(x,*) to v′(x+1/x-1,*). Edge e(s0,s1,s) is said
to be active when its outvertex and invertex are active and s0=Q.
An active directed path is a sequence of continuous active edges.
At the first stage, it guesses some active directed path Π from p0
to pY and at the next stage, checks it in polynomial steps outputting
the edges of Π on the output tape, and halts when it reached at pY/pN.
In the checking stage, it works like the following.
(1)Pointer Pt is at p0. Choice one of active edges e(q0,s1,s)
outgoing from p0. Write T[1]=s, set Q=s1, output e and forward
Pt to the invertex of e.
(2)Pointer Pt is resting on vertex v(x,y). Choice one of active
edges e(s0,s1,s) outgoing from v. Write T[x]=s, set Q=s1, output
e and forward Pt to the invertex of e.
(3)If the next state s1 of e is qY/qN, then halt else repeat (2).
(4)If w is acceptable with M, then this stage ends at most in n^k
steps of pointer Pt and each step of Pt is polynomial as above.
Theorem: AGM is NP-complete.
Proof: When NDTM M accepts input word w ∈ language L, it is sure
that there is an active directed path Π connecting p0 to pY and it
is easy to see that Π can be certified in polynomial time. as well
it is obvious that if w is not in L, then there is no such paths
in D. Hence AGM is in NP class. Next by definition, every language
L ∈ NP can be transformed to AGM in polynomial time since the
size of directed multi-graph D is polynomial of n such as O(n^k).
Note: a multi-tape TM can be emulated by some single-tape TM and
we can use some appropriate encoding scheme for AGM language. QED.
I wish you enjoy and love this machine.
Sincerely,
Michiro Nasu
a.k.a. Numskull Neophyte
nasukun@...
-------- Original Message No.0922
--------
Subject: [algorithm-forge] Holy Cow
Date: Sat, 24 Nov 2001 08:11:39 +0900
From: "Michiro Nasu"
To: algorithm-forge@yahoogroups.com
Holy Cow
Hi All!
as was introduced in my previous mail, I already showed that Cook's
theorem is wrong at theory-edge [1]. of course I know what it means.
Yap wrote at a footnote in his online book [2],
"Cook's theorem in Complexity Theory is comparable to G"odel's Incomplete-ness Theorem in Computability Theory: both play a paradigmatic role (in
the sense of Kuhn[3]). In Kuhn's analysis, a scientific paradigm involves
a system of views, methodology and normative values for doing research.
A further parallel is that the relation of P to NP can be compared to the
relation between the recursive sets and the recursively enumerable sets."
a Turing machine T (deterministic or nondeterministic) runs in polynomial
time if there is a polynomial function g(n) such that for every input of
length n any computation sequence of T halts in g(n) or fewer steps. the
problem class P(NP) is defined as that is recognized by deterministic
(non-deterministic) Turing machines which run in polynomial time.
Post [4] defined the two reducibility of many-one reducibility and Turing
reducibility in computable problem sets. what we know as Karp-reduction
and Cook-reduction are just the time bounded versions of those two
reductions defined by Post. since the notions of many-one reducibility
and Turing-reducibility were so effective tools in the recursive function
theory [5], it was quite natural to expect that those two reductions
would work in Complexity Theory as well as in Computability Theory.
I think Complexity Theory is not seamless with Computability Theory.
that is, it is problematic to adapt Post's reducibility to Complexity
Theory directly. listen to what Garey & Jonson [6] talking.
"We conclude that substantially new proof techniques will probably be
required to resolve the P vs. NP question, as well as the other related
questions we have mentioned. That is, if we can resolve them. Hartmanis
and Hopcroft [7] use relativization techniques like those mentioned above
to indicate at least possibility that questions like this one might be
independent of set theory, and hence not resolvable in our standard
system of logic."
AFAIK relativization technique was introduced by Solovay et al. [8].
For any set X, let P^X (NP^X) be the class of languages accepted in
polynomial time by deterministic (nondeterministic) query machines
with oracle X. P^X (NP^X) is the relativized version of class P(NP).
Solovay et al. proved that there exist oracles A and B such that
P^A=NP^A and P^B!=NP^B [8].
using our elementary terminology, this theorem may be expressed like
P=NP substantially and P!=NP substantially, simultaneously.
I already wrote regarding "P=NP substantially" in theory-edge at [9].
I'll recite it here for convenience. consider the following problems.
Hole Recognition with Constant K [HRCK]
Given: A graph G.
Property: G has a hole of size at least k constant.
Hole Recognition with Variable K [HRVK]
Given: A graph G and an integer k.
Property: G has a hole of size at least k.
Spinrad [10] showed that [HRCK] is in P and [HRVK] is NP-complete.
suppose a machine M1 to solve [HRCK] and M2 to solve [HRVK]. give them
a same problem, I.e., same G and k, and let them start. then they will
stop at an exactly same second. thus we have P=NP substantially.
polynomial problem [HRCK] can be reduced to NP-complete problem [HRVK],
but not vise versa. in this sense, "P is easier than NP" is still true.
however the infinite set of [HRCK] solvers solves all problems that are
solved by [HRVK] solver. the infinite set of [HRCK] solvers is nothing
but the oracle for [HRCK]. see also [11].
regarding P!=NP direction, consider Prime Problem. if the number is
expressed in unary, Prime Problem can be solved in polynomial time using
Eratosthenes' sieve. however in binary form the number m already becomes
2^n where n is the length of the input. it is quite reasonable to suppose
that the time complexity f(n) of the problem is at least proportional to
the size of the number m. hence we get f(n)≥2^n. although we don't know
the intrinsic complexity of the problem, exponential time can be considered
as the lower bound of the problem substantially. so we say, "P=NP and
P!=NP substantially, simultaneously". as the consequence of thouse, it
turns out that we can say neither P=NP nor P!=NP.
these observations is not at all the evidence of the flaw in Cook's
theorem but it reveals that the parallelism of Complexity Theory and
Computability Theory already broken.
in my next mail, I'll reconsider the completeness of problem classes.
Michiro
[1] Michiro Nasu, Departure from the Theology,
http://groups.yahoo.com/group/theory-edge/message/4323
[2] Chee K. Yap, Theory of Complexity Classes, 1998, available at
ftp://cs.nyu.edu/pub/local/yap/complexity-bk.
[3] Thomas S. Kuhn, The structure of scientific revolutions. Chicago Univ.
Press, 1970.
[4] E.L. Post, Recursively enumerable sets of positive integers and their
decision problems, Bull. AMS 50, 284-316, 1944.
[5] Richard E. Ladner, On the Structure of Polynomial Time Reducibility,
J. ACM 22:1, 155-171, 1975.
[6] Michael R. Garey, David S. Jonson, Computers and Tractability: A Guide
to the Theory of NP-Completeness, Freeman, New York, 1979.
[7] Juris Hartmanis, J.E. Hopcroft, Independence results in computer science,
SIGACT News 8:4, 13-24, 1976.
[8] Theodore Baker, John Gill, Robert Solovay, Realizations of the P=?NP
question, SIAM J. Comput. 4, 431-442, 1975.
[9] http://groups.yahoo.com/group/theory-edge/message/4271.
[10] Jeremy P. Spinrad, Some questions on holes,
http://groups.yahoo.com/group/theory-edge/message/4179.
see also: Marx Daniel, Re: Some questions on holes,
http://groups.yahoo.com/group/theory-edge/message/4202.
[11]Marx Daniel, Re: NP, the endless saga,
http://groups.yahoo.com/group/theory-edge/message/4272.
-------- Original Message No.4282
--------
Subject: [theory-edge] Re: Departure from the Theology
Date: Sun, 4 Nov 2001 15:40:59 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Re: Departure from the Theology
it's no problem to use Karp-reduction (polynomial-reduction)
under the assumption that P is easier than NP. however you have to notice that asking
the time complexity of any imaginary machine such as NDTM or
Oracle is absolutely nonsense. for example: suppose a polynomial
problem P1 and a NP-complete problem P2. when a DTM solves P1
in polynomial T(P1), no doubt that a NDTM also solves p1 in T(P1).
assume a NDTM solves P2 in polynomial T(p2). do you think it has
any sense to compare those complexity functions T(P1) and T(p2)?
Aho, Hopcroft and Ullman applied Karp-reduction to the proof of
Cook's theorem and they frankly confess that they use a NDTM
which solves the original problem and insist that it is done in
polynomial time. this is of course against the above principle.
Yap hadn't mentioned any such machine in his proof and hid it
behind the lengthy description. however this attempt is impossible
according to the opinion of Portia, the Doctor of Low.
M.N.
-------- Original Message No.4279
--------
Subject: [theory-edge] Re: Departure from the Theology
Date: Sun, 4 Nov 2001 02:59:38 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Re: Departure from the Theology
at first I want to make some minor correction and supplement
of my previous mail.
I wrote,
> what's the flaw of the procedure above? when we desire to show
> that problem A is at least as hard as problem B, we need the
> following condition.
the condition X is not the necessary condition that problem A
is as hard as problem B, but is a sufficient condition. so the
above should be rewrote like follows or else.
"what's the flaw of the procedure above? when we desire to show
that problem A is at least as hard as problem B using a
reduction method, we need the following condition."
this means that there may exist some other way than reduction
method to compare the tractability of two problems. however the
P-reducibility in Cook's proof is not the case at all.
I said "Cook's proof was wrong". but accurately it was not so.
because there is no faults in the description itself of the
proof. it just proved that every NP problem is P-reducible to
{DNF tautologies}. he did not show nor prove the necessary
theorem 0 stating that if problem A is P-reducible to problem
B, then B is at least as hard as A. if theorem 0 is provided
then theorem 1 turns out to state that {DNF tautologies} is
NP-complete. (apparently theorem 0 doesn't hold.)
however it's a simple fact that we are all considering that
Cook proved it. moreover all of books which refer to Cook's
theorem cite that Cook proved NP-completeness of SAT. hence
my argument hadn't missed the target.
had NP-completeness collapsed?
no. the NP-completeness is a fact. a fact is never to be lost.
how can we go without Cook's theorem? should we devise any
alternative for it?
we can go without the theorem and we need not any alternatives.
we will have SAT-compatible or SAT-equivalent class. it will
contain all of old NP-complete problems.
is the SAT-equivalent class is in NP?
yes of course. but if one finds an efficient algorithm for a
problem in the class, then the whole class moves to P. however
this time nothing will happen not like the case of NP=P. this
class is said to be a floating class or an island class.
SAT-equivalent problems is in XDTM class. I guess the XDTM may
be separated into 3 tiers.
tier 1. Graph Isomorphism, etc.
tier 2. SAT-equivalent class
tier 3. Prime Problem, etc.
Subgraph Isomorphism is in SAT-equivalent class and obviously
Graph Isomorphism is easier than Subgraph Isomorphism.
Corneil [1] even conjectured that it is in P.
my conjecture: SAT-equivalent may have O(n^logn) upper bound.
empirically this mark looks prospective.
if the number is expressed in unary, Prime Problem can be
solved in polynomial time using Eratosthenes' sieve. however
in binary form the number already becomes 2^n where n is the
length of the input. this bound cannot diminish.
I think this picture is rather natural and fits our wit.
M.N.
[1] D. G. Corneil and C. C. Gotlieb, An Efficient Algorithm
for Graph Isomorphism, J. Assoc Computing Machinery Vol.
17 No.1, 51-64, 1970
-------- Original Message No.4277
--------
Subject: [theory-edge] Departure from the Theology
Date: Sat, 3 Nov 2001 05:55:34 +0900
From: "Michiro Nasu"
To: theory-edge@yahoogroups.com
Departure from the Theology
Tarry a little; there is something else.
This bond doth give thee here no jot of blood;
The words expressly are 'a pound of flesh:'
Take then thy bond, take thou thy pound of flesh;
But, in the cutting it, if thou dost shed
One drop of Christian blood, thy lands and goods
Are, by the laws of Venice, confiscate
Unto the state of Venice.
---The Merchant of Venice
Dear Jerry and all!
you posted "Smaller open problems" on 9/6/2001 and I picked it at
9/26. we've worked for more than one month in the field where you
planted the seed and got so much crop from the field. I greatly
appreciate you for that. we learned that, for even the smallest
problems, it was very hard to get the lower bound of the
complexity, I.e., we were almost impotent to decide the intrinsic
complexity of any problem. on the middle of the way,
Guenter
proved that odd hole recognition passing through a given vertex
was NP-complete. the key concept there was "as hard as".
→see also
meanwhile we became aware of some interesting relation between a
polynomial problem and the NP-complete problem relative to it. we
understood that there was something to dig out. the key word was
"K constant". it involved the discussion of the tiers of
complexity and the border line between P and NP. now it is clear
for us that NP=P substantially.
finally we found out the paradox that Tortoise [DTM] was definitely
defeated by Achilles [NDTM] but the Tortoise Family [infinite set of DTM] was not. this
paradox was hidden in the Theory as Oracles. seemingly to learn
NP-complete problem is not to find a faster algorithm but rather
to solve the paradox. and then we constructed a real machine
family and analyzed it.
recall the table represented in my last mail. the real machine
family has three layers of DTM, XDTM and UXDTM. DTM corresponds
to the deterministic polynomial class. XDTM contains all of NP-
complete problems. UXDTM is slightly stronger than NDTM since it
can solve co-NP problems easily. however no problem, even though
we consider UXDTM almost equivalent to NP.
since the real machine representation of Oracles mounts the tiers
by one rank in general, it is considered that most optimization
problems which relate to NP-complete decision problmes are in
UXDTM. by definition, NP-complete problems must be as hard as any
other problems in NP. so the situation seems entirely irregular.
how can we relieve this? I think there is no way to escape from
it because this problem has been held long in the Theory and no
one could save it. if there is a way to escape the situation, it
is only to return to the starting point of the Theory. I went to
the point and found that Cook's theorem was wrong.
here is a proof that square detection problem is as hard as
triangle detection problem.
Graph Triangle Detection [GTD]
Given: a graph G.
Property: G has a triangle (I.e., a cycle of size 3).
Graph Square Detection [GSD]
Given: a graph G.
Property: G has a square (I.e., a cycle of size 4).
Proposition: [GSD] is at least as hard as [GTD].
Proof: there is a linear reduction from [GTD] to [GSD] as below.
ask the oracle for [GTD]. if the answer is YES then make graph G'
consisting of a square, else make graph G' consisting of a
triangle. it is easy to see that "G has a triangle" is equivalent
to "G' has a square". the time complexity to make G' is clearly
linear to n. QED.
what's the flaw of the procedure above? when we desire to show
that problem A is at least as hard as problem B, we need the
following condition.
Condition X: there is a reduction R from B to A and the time
complexity of R is smaller than the lower bound of
the time complexity of B.
note: that this condition does not admit the equality. if we
allow the complexity of a transducer being equal to the objective
problem, the transducer can simulate the solver and easily make
a fabrication.
we know that, in general it is almost impossible to decide the
lower bound of the complexity of a problem. so here is another
problem but I just appoint out for now that to apply polynomial-
reduction (known as Karp-reduction or many-one reduction), we
need the assumption that "P is easier than NP".
now let's observe the proof by Cook. the paper [1] consists of
eight pages and has four chapters. the body of the proof is in
the first chapter.
Definition: A set S of strings is P-reducible (P for polynomial)
to a set T of strings iff there is some query machine M and a
polynomial Q(n) such that for each input string w, the
T-computation of M with input w halts within Q(|w|) steps (|w| is
the length of w) and ends in an accepting state iff w in S.
Theorem 1: If a set S of strings is accepted by some
nondeterministic Turing machine within polynomial time, then S is
P-reducible to {DNF tautologies}.
clearly the time complexity of the oracle in query machine M
equals to the objective nondeterministic Turing machine in the
Theorem. I.e., Cook's proof is broadly infringing the condition
X. other authors who refer to Cook's proof avoid it and use
Karp-reduction transducers instead of P-reducibility in their
proof. however the situation is unchangeable.
the strategies of all of their proofs are similar. they make a
Boolean strings from the input w of the original problem and the
configurations in some accepting computation path of M on w. how
can you obtain the accepting path without letting the machine
run? if you know, please teach it to the pity Jew! I believe you
need no more devious explanation. Yap had left a note at the end
of Cook's proof in his book [2] saying,
"It is curious to observe that, with the exception of the first
condition, the rest of the clauses in Fn(x) are not directly
related to the input x."
I'm willing to admit the immeasurable greatness of the historical
work of Cook who established the concept of NP-completeness and
opened the new age of the Complexity Theory. the NP-completeness
is the treasure of the Theory like a beautiful coral reef in the
blue ocean. I admire him and appreciate his contribution to the
Theory. the scaffolding was necessary to build up the cathedral
but when the construction has been done, it has to be dismantled.
in my next mail, I'll seek the way to reconstruct the Theory.
with best wishes,
Michiro Nasu
email: nasukun@...
URL: http://www.aya.or.jp/~nasukun/
[1] Steven A. Cook, The complexity of theorem-proving procedures,
3rd Proc. ACM symp. on Theory of Comp. Sci., 151-158, 1971.
[2] Chee K. Yap, THEORY OF COMPLEXITY CLASSES, 1998, available at ftp://cs.nyu.edu/pub/local/yap/complexity-bk.