On computational complexity
- From: "Artyom" <Artyom.Chernikov@xxxxxxxxx>
- Date: 26 Nov 2006 07:23:31 -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
.
- Prev by Date: Re: Conditional Probability Relations Question
- Next by Date: Re: Conditional Probability Relations Question
- Previous by thread: Computational complexity question
- Next by thread: Definition of locally convex space
- Index(es):
Relevant Pages
|
