On computational complexity
- From: "Artyom" <Artyom.Chernikov@xxxxxxxxx>
- Date: Mon, 27 Nov 2006 14:00:09 +0000 (UTC)
1) What is the computational complexity of determining whether given
graph is a Paley one? Some hardness/completeness result is highly
desired.
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: Optimal Partitioning of an Undirected Graph Using Matroids
- Next by Date: Re: who know how to solve this nonlinear diophantine equation
- Previous by thread: Optimal Partitioning of an Undirected Graph Using Matroids
- Next by thread: Finding x of hypergeometric 2F1[a,b,c,x] ?
- Index(es):
Relevant Pages
|
