np-hardness

  1. Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

  2. Functions that are Not Efficiently Computable but Learnable
  3. Matrix Coloring under Vertical and Horizontal Constraints

  4. Reduction of graph chromatic number to hypergraph 2-colorability

  5. Check the match of the maximum of each subset

  6. Geometric max cover

  7. Proving NP-complete problem
  8. Everyday encounters with NP-complete problems
  9. An optimal subspace projection problem
  10. Maximum Polyhedron Volume in Given $n$ Points
  11. Hardness of exact binomial tail bounds

  12. What are some problems in $P$ which have lower bounds assuming that $P \neq NP$ or the ETH?

  13. Solving linear program with 1 quadratic constraint complexity
  14. Is TSP in the plane with rational coordinates NP-complete?

  15. Is the N Queens problem NP-hard?

  16. Is Asymptotic PTAS $\subseteq$ APX?

  17. String version of even-odd partition problem
  18. Are there NP-complete problems with polynomial expected time solutions?
  19. Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
  20. Tardos Function Counterexample to Blum's $P\neq NP$ Claim
  21. $k$-clique in $k$-partite graph
  22. Clique cover problem
  23. Max weight travel on a graph with deadline

  24. Max-weight connected & co-connected subgraph problem
  25. Determining what can be achieved by a permutation of elements of a noncommutative group
  26. Is deciding whether all satisfying assignments are NAE assignments coNP-complete?

  27. Does a weighted graph have a path with weight zero?

  28. How to show this problem is hard?
  29. What is the computational complexity of this SAT Variant

  30. Is optimally solving the n×n×n Rubik's Cube NP-hard?

  31. A conceptual question regarding hardness proofs by reduction

  32. Is pooling-aware bin packing NP-Hard?

  33. totally-mixed 2SAT with exact cardinality?
  34. Is this vertex ordering optimization NP-Hard?
  35. Limits of variants of Independent Set?

  36. When does "X is NP-complete" imply "#X is #P-complete"?

  37. Does P = NP imply NP being a strict subset of PSPACE?

  38. Is the following problem NP hard?

  39. Is intersection of $k \ge 3$ graphic matroids in P?
  40. Is approximating Exact Set Cover NP-hard for constant approximation factor? ETH hard?

  41. Vertex isoperimetric number of a graph - NP-hard?

  42. Sparse coding and matching pursuit algorithms

  43. Complexity of a subset sum variant

  44. Hard extendability problems
  45. An NP-complete variant of factoring.
  46. An edge partitioning problem on cubic graphs
  47. Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

  48. Exact Algorithms for r-Dominating Set on Bounded Treewidth Graphs

  49. What are the best known reductions from SAT to CNF-SAT?

  50. Are there interesting graph classes where the treewidth is hard (easy) to compute?

  51. Can we fast generate perfectly uniformly mod 3 or solve NP problem?

  52. A maximization problem containing summation and multiplication

  53. Completeness and Context-Sensitive Languages.

  54. Hardness of finding roots of a degree $2$ polynomials over $\mathbb{F}_2$
  55. Any fast algorithm for minimum cost feedback arc set problem?

  56. Kth best problem that is NP-hard for K polynomial
  57. Complexity of Underdetermined Systems
  58. Reduction Unbounded Knapsack < k-Exact Unbounded Knapsack

  59. On integer programming
  60. Computational Complexity of cycle double cover

  61. NP-Complete problems that admit an efficient algorithm under the promise of a unique solution

  62. How hard is PromiseFlowFree?

  63. Examples of "Sandpile" TSP Instances

  64. Did "Where the really hard problems are" hold up? What are current ideas on the subject?

  65. ETH-Hardness of $Gap\text-MAX\text-3SAT_{c}$
  66. Graph optimization problem with multiple objectives/constraints

  67. Some questions about the Ryan O'Donnel and Yuan Zhou's paper "Approximability and proof complexity"

  68. Can the Lasserre relaxation be defined over the reals?
  69. Is there a natural problem on the naturals that is NP-complete?

  70. Proof that the graph optimization problem is NP-hard

  71. SOS and the small set expansion property

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

  73. How does one know what is not in a certain class of pseudo-distributions?

  74. Validity of exponentiation in a polynomial time reduction

  75. Post Correspondence Problem "binary" variant

  76. Given a matrix $A$ maximize the number of positive elements in $Ax$ under specific constraints for $x$

  77. Finding a positive point for a collection of polynomials

  78. At what parameters is following $NP$-hard?
  79. Consequences of a distillation algorithm for PSPACE

  80. On the shortest vector problem (is it $NP$-complete?)
  81. complexity of a constraint satisfaction promise problem
  82. Triangle arrangement problem
  83. Set cover problem with the same amount of sets and elements
  84. Maximum stable matching/allocation

  85. Is there any relationship of hardness between the two problems?

  86. NP-completeness of a specific topological sorting problem
  87. Hardness of $k$-Plex

  88. From Lasserre maps to pseudo-distributions

  89. $NP$-completeness of recognizing the difference of two permutations
  90. Positive 1-in-3 SAT FPT or Fixed Parameter Intractable
  91. What are the hardness results known for CSP over $\mathbb{F}_q$?

  92. Positive topological ordering, take 3

  93. Does the problem "partition a vertex-weighted graph into $k$ balanced connected parts" have a standard name?
  94. Directed NP-hard problems on DAGs

  95. What are the complexities of the following SAT subsets ?

  96. Is sparse embedding of a NP-complete problem in a polynomial problem NP-complete?

  97. Minimum-weight feedback edge set in undirected graph - how to find it? Is it NP hard problem?

  98. Given oracle for Max-3SAT compute clauses that cannot be satisfied

  99. Complexity of edge coloring in planar graphs

  100. Solution/Hardness of the following (integer) budgeted problem?