Re: Question on computational complexity
- From: "Proginoskes" <CCHeckman@xxxxxxxxx>
- Date: 27 Nov 2006 14:00:59 -0800
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.
--- 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
.
- References:
- Question on computational complexity
- From: Artyom
- Question on computational complexity
- Prev by Date: Re: Question on computational complexity
- Next by Date: Is there a known algorithm to solve this "playoff ranking" problem?
- Previous by thread: Re: Question on computational complexity
- Next by thread: Water surface in hexahedron
- Index(es):
Relevant Pages
|
