complexity-theory

  1. Time complexity bounds for the approximation of optimal values for bounded linear programs
  2. Subset Sum for {1,...,n}

  3. Which NP complete problem is this?

  4. Relation among $GapP, \#P, PP$ and $CH$
  5. Circuit Lower bound for $EXP^{NP}$
  6. Is a minimal deviation version of set partition problem NP-Hard?

  7. Linear time reduction equivalence

  8. Reduction — Do they work for unrelated problems?

  9. Is this summation from an insertion sort complexity analysis correct?

  10. Containment of ACC$^0$ in TC$^0$
  11. References for the computational complexity of training neural networks

  12. A clarification on $NP=coNP$?
  13. Computational Complexity and P vs. NP, A New Insight

  14. What is the consequence of $\oplus P\neq PP$?

  15. is P_CTC = BPP_PATH?

  16. Array with queries to decrement or find sum of range

  17. Simulating Turing Machine with writing only on non-input fields on read-only Turing machine
  18. Is there an algorithim to construct a graph with an even number of vertices, and each vertex has k edges?
  19. How do I develop a structured work method for theoretical computer science?
  20. How to prove QUADPROG is NP-hard using 3COLOR?
  21. Why Can't Reverse Hashing Prove $P \neq NP$?

  22. Can I assume every clause of 3SAT has one positive literal?
  23. NP Complete Proof - Polynomial Reduction
  24. Limited oracle TM

  25. Why not a $coNP$ hierarchy?

  26. Proving or disproving a set of total functions is countable

  27. On the exponential hierarchy?

  28. Recursive definition of a language $ L $ over $ \{a,b\} $
  29. Computational Irreducibility

  30. Show that maximum disjoint set problem is NP Complete
  31. Integer Programming Complexity
  32. On $NP=\Sigma_2^P$ from non-deterministic time?

  33. P-Completeness and Parallel Computation

  34. How does the computational complexity of problems depend on the model specifics of a register machine?

  35. Is packing a bag of presents easier for Rupert than Santa?

  36. Reduction of Hamiltonian cycle to Hamiltonian cycle & clique
  37. Non-deterministic logarithmic time complexity class
  38. $P/poly$ as oracle to itself?

  39. Do we know if there is an oracle $B$ so that $P^B \neq NP^B$ but $coNP^B=NP^B$?

  40. Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?

  41. On the Impagliazzo-Wigderson condition for derandomization

  42. Natural logspace complete problems
  43. NP-hardness of maximum set cover with element-level submodular function

  44. Max-min of a nonconvex quadratic problem

  45. NP hardness of partitioning a graph into two subgraphs
  46. Meaning of the Time Hierarchy Theorem

  47. NEXP = Σ$_2$ ⟹ NEXP = MA?

  48. Given a $NP$ complete decision problem, reduce the search problem of finding verifier to decision problem?
  49. Solve Time Complexity problem using Time Hierarchy

  50. Problems for which there is no algorithm with smallest time complexity

  51. Does NP ⊆ Co-NP imply NP = Co-NP?
  52. How would one reduce HaltTM to ATM

  53. Consequences from a lower bound of SAT problem
  54. Proving that a Turing machine decides a language in NP

  55. Is there a set of NP-hard problems that are most commonly used for proving NP-hardness?
  56. Is there a concept of information that distinguishes between "computed" and "non-computed" information?
  57. Soft Question: Looking for resources on computation over reals
  58. How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$
  59. Does co-TIME(f(n)) = TIME(f(n)) and co-SPACE(f(n)) = SPACE(f(n))?

  60. Graph coloring decision problem NP-complete

  61. P class definition in Garey and Johnson's Computers and Intractability

  62. How to prove that $nlog(n)$ is space constructible?

  63. Trying to find Worst Case complexity

  64. Decide whether there is an integral legal s − t flow in G
  65. If everyone believes P ≠ NP, why is everyone sceptical of proof attempts for P ≠ NP?

  66. Show that Knapsack-like problem on directed graph is NP-hard
  67. Longest palindrome size with suffix trees
  68. Relations between DSPACE and NSPACE

  69. Clarification on a theorem?
  70. Partition a set of multisets into increasing sequences of inclusion

  71. Why always NP-complete to prove NP-hard?

  72. Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make?

  73. On $BPP\not=SUBEXP$ and $SUBEXP\not\subseteq P/poly$?
  74. Reducing Clique to Independent Set

  75. When represented as a function, why is the input of a decision problem a natural number?

  76. Hardness of checking maximal magnitude of a sum of a subset of vectors
  77. Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$?
  78. Interactive protocols for showing knots are "hard" to untie
  79. Reduction of graph chromatic number to hypergraph 2-colorability

  80. How does SETH implies ETH?

  81. Find Length of longest substring with all 1's in a binary string with k queries

  82. Algorithm for finding factor pairs

  83. Find the flaw in the P != NP proof

  84. How to prove the NP-completeness of 15-Partition Problem
  85. Why doesn't descriptive complexity theory solve P = NP?
  86. Inductive proof that $n^2 + bn + d$ is $O(n^2)$ using definition of big O

  87. How to prove that matrix multiplication of two 2x2 matrices can't be done in less than 7 multiplications?
  88. Reducing Exact Cover to Subset Sum

  89. What is Geometric complexity theory (GCT)?

  90. Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

  91. Show a problem using one approach is at least as hard as using another approach
  92. Complexity of feasibility of a certain weighted digraph problem
  93. IN-SPACE ACCEPTANCE Problem is PSPACE-complete
  94. Is $Ω(n\log ⁡n)$ the lower-bound for *all* sorting algorithms or *just comparison-based* sorting algorithms?

  95. Why the restriction on the length of the proof in a $(r,q)$-verifier in PCP is inconsequential?

  96. Why polynomial time is called "efficient"?

  97. Communication complexity of string matching
  98. On non-determinism with $\oplus P$ oracle

  99. Show that problem of Shortest-Path in digraph is in NL

  100. Limited sort: is this a well-known problem?