complexity-classes

  1. On $NP$, $\oplus P$ and $PP$?
  2. When it is said an algorithm runs in exponential time, is it meant it has complexity O(2^n), or 2^O(n)?
  3. Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?

  4. Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

  5. A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?

  6. What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$
  7. Two queries related to Toda

  8. Proving NP-complete problem

  9. Is there any known Poly-APX-complete minimimization problem?

  10. Approximation class of finding decision trees with minimal depth

  11. Difference between $Max-SNP_0$ and $Max-SNP$

  12. On collapsing the Exponential time hierarchy

  13. What happens when PSPACE contains NEXP?
  14. Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?
  15. Almost-P and related definitions

  16. #P-complete problem whose decision version is in P

  17. What is the relation between P-immune languages and NP-complete languages?
  18. When studying the computational complexity of functions $\{0, 1\}^\ast \to \{0, 1\}^\ast$, is it enough to restrict to $\{0, 1\}^\ast \to \{0, 1\}$?

  19. Is there an inherently ambiguous language which can not be recognized by Deterministic LBA?

  20. Time Hierarchies in DSPACE(O(s(n)))
  21. Is sliding blocks linear space complete?

  22. Example of something that’s different for generic and random oracles?

  23. In what class are randomized algorithms that err with exactly 25% chance?
  24. Complexity Class Equalities on the Edge of Inconsistency

  25. Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
  26. Is Asymptotic PTAS $\subseteq$ APX?
  27. Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$
  28. Power of randomness vs. power of indefinite computation
  29. Logarithmic levels of the polynomial hierarchy (below PSPACE)
  30. Is there known any complexity class containing online counterparts of optimization problems?
  31. Is Norbert Blum's 2017 proof that $P \ne NP$ correct?

  32. What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?
  33. Tardos Function Counterexample to Blum's $P\neq NP$ Claim
  34. Cases of Linear programming known to be in $NC$?
  35. An analog of DP for the second level of the polynomial hierarchy

  36. Oracle comparing $EXP$ with $UP$
  37. A succinct version of permanent that is $EXP$-complete

  38. variant of Critical SAT

  39. Dp completeness of a problem

  40. What does $\#P\subseteq FP^{PPAD}$ imply?
  41. Closure properties of $L$ (DLOGSPACE)?

  42. On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?

  43. $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$

  44. A uniform computability model to define time and space complexity (even in the sublinear case)

  45. DTIME and PSPACE

  46. On status of Valiant's $NC^2=P^{\#P}$ provability program?

  47. On $\Delta_i^P$
  48. How to show this problem is hard?

  49. What is the complexity of computation of zero point by Rieman zeta function?

  50. Co-Partition Problem: Why is this proof for it being in NP wrong?
  51. ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
  52. Descriptive model theory classification of Counting hierarchy

  53. Is there a computing problem which is in quasi-polynomial time but is (maybe) not in $\beta P$?

  54. On $NP$ and $XP$ classes?
  55. Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

  56. Intermediate problems between PSPACE and EXPTIME

  57. Complexity of comparison unary>binary

  58. Can one amplify P=NP beyond P=PH?

  59. Is finding a solution harder than verifying a solution?

  60. A question of relationships between #P and PSPACE

  61. k-Vertex Cover problem is in parameterized Log space

  62. Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?
  63. Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

  64. Looking for approximation class between NPO and Exp-APX

  65. Does the existence of an RP-complete language imply P = RP?

  66. Running multiple rounds of a BQP computation, without multiple measurements?

  67. Why are these two definitions of PPAD equivalent?

  68. Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?
  69. What's the relationship between ASP-complete and #P-complete?

  70. possible bridge between group growth theory and complexity theory?

  71. $NotTooManyP^{cc}$ class in communication complexity
  72. Conjecture: All FPT NP-complete languages are fixed-parameter-isomorphic

  73. Non-trivial PCP characterizations of complexity classes beyond ELEMENTARY?

  74. Finding a certificate if E=NE
  75. What can we say about AM[log n]?

  76. Permanent in Bounded error Quasi Poly time

  77. Non-uniform version for the whole polynomial hierarchy

  78. Evidence that PPAD is hard?

  79. 2-NEXPTIME-complete problems

  80. What is an equivalent definition of mP/poly in terms of a Turing machine?

  81. Is the class NSC closed under complement?

  82. Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

  83. Why are these two definitions of PLS equivalent?

  84. Is the difference of two languages in NP-complete an NP-complete too?
  85. Circuit complexity class of polynomial factoring and Hensel lifting in Zassenhaus' algorithm?
  86. Is counting the words in a finite regular language #P-complete?

  87. The relation between RP, BPP and NP
  88. Statements that imply $\mathbf{P}\neq \mathbf{NP}$

  89. Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?

  90. Syntactic Complexity Class ${\bf X}$ such that ${\bf PP} \subseteq {\bf X} \subseteq {\bf PSPACE}$

  91. XOR-SAT to Horn-SAT reduction

  92. Complexity of permanent modulo prime

  93. Why is it so difficult to study Sum of Squares (SoS) algorithms with degree $d>4$?
  94. Complexity involving connected components of 0/1 matrix

  95. An oracle in $\mathsf{NEXP}$ that separates ZPP from BPP
  96. Subexponential algorithms vs separations

  97. Is there a certificate definition for polyL?

  98. What are the hardness results known for CSP over $\mathbb{F}_q$?
  99. Is there any good literature on the computational complexity of function problems?
  100. What are the complexities of the following SAT subsets ?