complexity-classes

  1. PromiseBQP and expectation values of operators
  2. Why are circuit classes AC0, ACC0, etc. unavoidable?

  3. Efficiently computable by a "simple" algorithm?

  4. What are semantic classes that have a syntactic equivalent?

  5. Benefits for syntactic and semantic classes
  6. What are the problems in EXPSPACE \ {NEXP ∪ co-NEXP}?

  7. Reduction from SAT to binary matrix subset problem

  8. Find a pair of nodes with maximum sum of distances in k given trees

  9. If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?
  10. Complexity of testing if two sets of $m$ points in $\mathbb{R}^n$ differ only by rotation?

  11. Printing all paths of a tree and sorting the weight of edges

  12. NEXP-complete problems
  13. Complexity of modal logic IK5

  14. Kolmogorov generic oracle
  15. Using idea of entropy (maybe Shannon entropy or other continuous entropy) to the topic of functional analysis

  16. Does the NP-hardness of finding any valid solution imply NPO-hardness?
  17. Should GCT focus on $PSPACE\not\subseteq P/poly$?
  18. What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
  19. On sparse complete sets and P vs L
  20. What is the complexity class most closely associated with what the human mind can accomplish quickly?

  21. Relation between transcendental numbers and computational complexity?
  22. How to charactorize computational complexity based on finding solution to algebraic equations?
  23. An oracle that separates BPP from PP?
  24. Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

  25. Random self reducibility and NP

  26. On $NP$, $\oplus P$ and $PP$?

  27. On reduction between two classes?

  28. What is conjunctive truth table reduction?
  29. Cases of Linear programming known to be in $NC$?

  30. Does Kannan's theorem imply that NEXPTIME^NP ⊄ P/poly?
  31. Problems in NC not known to lie in NC2
  32. Problems in $\mathsf{NC^{2}}$ that are not known to be in $\mathsf{AC^{1}}$ or $\mathsf{DET}$
  33. Problems outside of P that are not P-hard

  34. Recursively presenting or even enumerating all P-hard languages
  35. Sufficient conditions for the collapse of Polynomial Hierarchy (PH)

  36. A class of languages admitted by a class of grammars equivalent to $\mathbf{PR}$?
  37. What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$

  38. Two queries related to Toda

  39. Proving NP-complete problem

  40. Are $BPP^{BPP^{\oplus P}}$ and $BPP^{NP}$ contained in $BPP^{\oplus P}$?

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

  42. Approximation class of finding decision trees with minimal depth

  43. Difference between $Max-SNP_0$ and $Max-SNP$
  44. On collapsing the Exponential time hierarchy

  45. What happens when PSPACE contains NEXP?

  46. Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

  47. Almost-P and related definitions

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

  49. What is the relation between P-immune languages and NP-complete languages?
  50. 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\}$?

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

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

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

  55. In what class are randomized algorithms that err with exactly 25% chance?

  56. Complexity Class Equalities on the Edge of Inconsistency
  57. Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
  58. Is Asymptotic PTAS $\subseteq$ APX?

  59. Classes between $\textbf{PSPACE}$ and $\textbf{EXP}$

  60. Power of randomness vs. power of indefinite computation
  61. Logarithmic levels of the polynomial hierarchy (below PSPACE)

  62. Is there known any complexity class containing online counterparts of optimization problems?

  63. Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
  64. What are examples of complexity classes that have contradictory relativizations but they were proven to be either equal or unequal?

  65. Tardos Function Counterexample to Blum's $P\neq NP$ Claim

  66. An analog of DP for the second level of the polynomial hierarchy
  67. Oracle comparing $EXP$ with $UP$

  68. A succinct version of permanent that is $EXP$-complete
  69. variant of Critical SAT
  70. Dp completeness of a problem

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

  73. On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?
  74. $\mathsf{NP^{PP}}$ vs $\mathsf{P^{PP}}$
  75. A uniform computability model to define time and space complexity (even in the sublinear case)
  76. DTIME and PSPACE

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

  78. On $\Delta_i^P$

  79. How to show this problem is hard?

  80. What is the complexity of computation of zero point by Rieman zeta function?
  81. Co-Partition Problem: Why is this proof for it being in NP wrong?
  82. ${\bf NP} \not = {\bf E}$ and ${\bf PSPACE} \not = {\bf E}$
  83. Descriptive model theory classification of Counting hierarchy

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

  85. On $NP$ and $XP$ classes?

  86. Consequences of $\oplus \mathbf{P} \subseteq \mathbf{NP}$

  87. Intermediate problems between PSPACE and EXPTIME
  88. Complexity of comparison unary>binary
  89. Can one amplify P=NP beyond P=PH?
  90. Is finding a solution harder than verifying a solution?

  91. A question of relationships between #P and PSPACE
  92. k-Vertex Cover problem is in parameterized Log space
  93. Is BQP equal to BPP with access to an Abelian hidden subgroup oracle?

  94. Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

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

  96. Does the existence of an RP-complete language imply P = RP?
  97. Running multiple rounds of a BQP computation, without multiple measurements?

  98. Why are these two definitions of PPAD equivalent?

  99. Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

  100. What's the relationship between ASP-complete and #P-complete?