Information Technology Reference
In-Depth Information
2.4 Universal Relations
All of the NP-complete sets that are p-isomorphic to SAT have a padding function,
and even the NP-complete sets that are not known to be p-isomorphic to SAT (such
as certain
k
-creative sets, and sets of the form
f
(SAT) where
f
is one-way) have
“padding” functions if we drop the requirement of invertibility (i.e., a reduction from
A
×
∗
to
A
that is one-one and length-increasing, but is not necessarily invertible).
Similarly, all known NP-complete sets are disjunctive-self-reducible. (A set
A
is
called “disjunctive-self-reducible” if there is a polynomial-time-computable function
that takes a string
x
as input, and produces a list
y
1
,...,
y
as output, such that
O
(
1
)
|
x
|
x
A
.)
Agrawal and Biswas defined two operators on relations (which they name the
join
and
equivalence
operators) that are related to paddability (without invertibility) and
disjunctive-self-reducibility, respectively (in the sense that if the witness relation for
aset
A
has the given operator computable in polynomial time, then
A
is paddable
or disjunctive-self-reducible, respectively). Remarkably, they were able to show that
the relations with these two operators are
precisely
the relations from which any
other NP-witness relation can be “recovered” in a fairly natural sense. (The details
of these definitions will not be repeated here; see [
AB92
]).
One thing that I particularly like about [
AB92
] is their presentation of a new class
of NP-complete sets. Let
f
be
any
one-one and size-increasing polynomial function.
They define a relation
R
f
as follows:
A
iff
iy
i
3
and one of the
(
z
,w)
R
f
if
|
w
|=
4
|
z
|
following three conditions hold:
1.
|
z
|=
1 and
w
{
0100
,
0101
,
0110
,
0111
,
1001
,
1010
,
1011
}
.
#
r
x
1
#
2. For some
r
>
0
,w
=
w
1
##
x
2
#
w
2
##
...
##
x
n
#
w
n
, where
f
(
1#
x
1
#
x
2
#
...
#
x
n
)
=
z
and for all
i
ↆ
n
,(
x
i
,w
i
)
R
f
.
#
r
x
#
i
1
#
i
2
#
w
∈
, where
3. For some
r
>
0
,w
=
...
#
i
n
#
j
1
#
...
#
j
n
##
f
(
1#
x
#
i
1
#
...
#
i
n
#
j
1
#
...
#
j
n
)
=
z
and for each
k
ↆ
n
,
bits number
i
k
and
j
k
of
w
∈
are the same.
Agrawal and Biswas show that
is NP-complete. I know of no
direct
way to see that this set is NP-complete; the proof of completeness presented
by Agrawal and Biswas follows because the relation
R
f
is universal (because it has
the required join and equivalence operators). It would be interesting to know if there
is any example of a natural NP-complete problem, for which it is easier to prove
NP-completeness by presenting the join and equivalence operators, than to present
a traditional
{
x
:
y
(
x
,
y
)
R
f
}
p
m
reduction.
The theory of Probabilistically-Checkable Proofs tells us that problems inNP have
witness relations with very special encoding structure. It would be interesting to know
if this body of knowledge can be merged with the theory of universal relations, to
obtain any new insights.
Figures
2.2
,
2.3
and
2.4
shows inclusion relations among the different notions
considered in this survey, all of which present ways to give a mathematically precise
definition that can serve as a proxy for the vague concept of what it means to be a
“natural” NP-complete set:
ↆ
