Computational complexity question
- From: "Artyom" <Artyom.Chernikov@xxxxxxxxx>
- Date: 26 Nov 2006 07:12:33 -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 = { x \in Graphs |
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: A problem I cannot solve
- Next by Date: Re: Conditional Probability Relations Question
- Previous by thread: A question in CONCRETE MATHEMATICS
- Next by thread: On computational complexity
- Index(es):
Relevant Pages
|
