Skip to content


Subversion checkout URL

You can clone with
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

33 lines (31 sloc) 1.901 kB
* intermediary.tex: change L(P_i) to A_i and L(Q_i) to B_i?
* is it necessary to require polynomially clocked TM?
* show that GI <_ker A (from thm:npeqcnpc), providing an upper bound in NPEq
* given an arbitrary NPEq complete language in which some equivalence classes
are finite, construct another language (polytime kernel reducible to it or
from it) in which all equivalence classes are finite
* examine NP disjoint pairs:
* and canonical proof systems:
* from josh: is the converse of open problem 5.5 true? in other words, IF a
class of equivalence problems has a complete problem, MUST our problem also
be complete? As evidence, consider that most reasonable complexity classes
have a complete problem which looks like this...see for example Sipser, "On
relativization and the existence of complete sets" Theorem on page II.
* easier perhaps: if L is CEq-complete then C = coC?
* also: maybe if there is a NPEq complete problem, then NP=coNP?
* an equivalence relation can be considered as a graph consisting of the union
of disjoint cliques (the equivalence classes)---does this help us lower the
complexity of anything? (for example, deciding if a set is an eq. rel. is
equivalent to determinining if each connected component is a clique [but
there could be exponentially many connected components], or using the
complement of clique, independent set, to do something with the complement
of an equivalence relation)
* Use github issues instead of this TODO file.
* check that the number of equivalence classes of the PSPACEEq complete problem
is not sparse
* show that a Sigma_k-complete problem implies a Sigma_k+1-complete problem
* Do arbitrary \mathcal{C}-complete graph properties exist? What is a graph
property which is in \Sigma_2?
Jump to Line
Something went wrong with that request. Please try again.