Re: Question on computational complexity
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 7 Dec 2006 22:39:03 -0800
Proginoskes wrote:
Artyom wrote:
1) What is the computational complexity of determining whether given
graph is a Paley one? Some hardness/completeness result is highly
desired.
I checked MathSciNet, and it doesn't appear that anyone has
investigated this question. Clearly, the recognition problem for Paley
graphs is in NP.
Maybe not as obvious as I thought.
A problem in NP is one such that there is a "polynomial-sized object"
which verifies that the input satisfies the definition. Here, that
object would be a bijection from V(G) to {0, 1, 2, ..., n-1} such that
(*) f(u) - f(v) or f(v) - f(u) is a quadratic residue modulo n, for
all edges uv.
In particular, if you are given a bijection, you can check whether (*)
is true in polynomial time.
A problem is in NP if there is a polynomial-time algorithm where you
are allowed to "guess" a bijection that satisfies (*), in the sense
that if there is a bijection which makes (*) true, you will "guess" a
bijection for which (*) is true.
Given a graph G, the following is an NP algorithm for determining
whether G is a Paley graph:
(1) Create ("guess") a bijection f from V(G) to {0, 1, 2, 3, ..., n-1}.
(2) Generate the quadratic residues mod n. {1^2, 2^2, ..., (n-1)^2}
(3) For every edge uv of G, if f(u) - f(v) is not a quadratic residue
mod n and
f(v) - f(u) is not a quadratic residue mod n, then return NO.
(4) Return YES.
Clearly the algorithm above runs in polynomial time (with respect to
n). A nondeterministic machine, running this program, will do the
following on step (1):
(a) If it is possible for this program to return a YES, the machine
will choose a bijection which leads to a YES answer; and
(b) If this program returns NO, no matter which bijection is picked, an
arbitrary bijection is picked.
A clearer example would be the following program, which on a
nondeterministic machine determines whether n is composite:
(1) Choose an integer k between 2 and n/2.
(2) If n/k is an integer, return YES.
(3) Else return NO.
What happens if we run this program with n=12? Well, there is an
integer k between 2 and 6 such that 12/k is an integer, so the machine
will choose one of these numbers; it will not choose 7, for instance.
(That's the rule for nondeterministic machines.) So maybe it chooses 3,
does the division, and returns YES.
What if the machine is given n=17? There is no integer k between 2 and
8 such that 17/k is an integer, so the machine will pick some integer
between 2 and 8 (it doesn't really matter which), find out that 12/k is
not an integer, and will thus return NO.
--- Christopher Heckman
2) The same question for the following set
S_f = { x is a complete k-partite graph and k is greater than f(|x|)
and size of each independent set in partition is greater than f(|x|) }
where |x| is order of graph x and for f we can take arbitrarily
monotone fuction?
3) Can we have in general a set of graphs(or any other structures as
well) hard for some complexity class not weaker than LOGSPACE such that
all its large enough members look quite similar. Some strict statement
of what "similar" means is here, for example:
http://groups-beta.google.com/group/sci.math/browse_thread/thread/9d100bc307771720
.
- Prev by Date: Re: maximal 3-colorable subset
- Next by Date: Re: Flow Decomposition
- Previous by thread: Re: maximal 3-colorable subset
- Next by thread: using non determinstic TM to prove NP is closed under kleene closure
- Index(es):
Relevant Pages
|
