Question on computational complexity
- From: "Artyom" <Artyom.Chernikov@xxxxxxxxx>
- Date: 26 Nov 2006 11:45:35 -0800
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
.
- Follow-Ups:
- Re: Question on computational complexity
- From: Proginoskes
- Re: Question on computational complexity
- From: Anuj Dawar
- Re: Question on computational complexity
- Prev by Date: Re: Discussion regarding Mr. Diabys algorithm
- Next by Date: Re: Discussion regarding Mr. Diabys algorithm
- Previous by thread: i want paticipate
- Next by thread: Re: Question on computational complexity
- Index(es):
Relevant Pages
|
