# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,944 questions
Filter by
Sorted by
Tagged with
5k views

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below: The original algorithms,...
• 331
95 views

There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem. The problem gives you an input of $n$ integers called grants $g_1 ... ... 1 vote 0 answers 55 views ### Complexity Lower Bounds for 3D Sparse Gaussian Elimination I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ... • 111 -4 votes 1 answer 27 views ### Help find algorithm for array-based task Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)? What is the solution? My solution is not ... • 11 12 votes 0 answers 352 views ### NP complete problem help I'm currently trying to find a reduction to this problem: Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ... 1 vote 0 answers 78 views ### Complexity class name for the class of languages that are$\Sigma^1_1$-definable over finite domains Let${\cal L}=\{Y_1,..., Y_k, X\}$be a finite relational language such that$X$is a unary relation name. Let$\phi(X,\bar{Y})\in{\cal L}$be a first-order formula (the formula can have the equality ... 1 vote 0 answers 216 views ### Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP? Underlying motivation for the question: if someone showed that$\text{P}=\text{NP}$but the algorithm thus produced for, e.g.,$3\text{-SAT}$, runs in time$\Omega(n^G)$where$G$is Graham's number, ... • 1,510 2 votes 1 answer 129 views ### Computational complexity problem book with solution recommendation? I will be taking complexity class next quarter and we will use the book "B. Barak, S. Arora, Computational Complexity: A Modern Approach". However, I have little exposure to complexity ... 10 votes 0 answers 175 views ### Provable BPP Hierarchy No Time Hierarchy theorem is known for$\mathsf{BPTIME}$, however, consider the following simple modification of the definition: A language is in$\mathsf{ProvableBPTIME}[f(n)]$if there is a ... • 13.8k 5 votes 2 answers 257 views ### Can we recover integers$a_i$from the sum$a_0 + a_1e+a_2e^2+\cdots+a_ne^n$? Since$e$is transcendental, the function$f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$is injective,$$f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ... • 1,879 1 vote 0 answers 52 views ### Living in Minicrypt, but sampling hard instances without the solution In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist. In other words, we can sample hard-on-average instances of NP complete problems. Question: Is living in Minicrypt, where ... • 197 1 vote 1 answer 136 views ### Complexity of a satisfiability problem I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below. Given$n$... • 13 2 votes 1 answer 138 views ### Complexity of MAX-ONEs Monotone 2-SAT with$n^{3/2}$or$C n^2$clauses? Let$\phi$be negative monotone 2-CNF on$n$variables and$n^{3/2}$clauses. What is the complexity of finding satisfying assignment with maximum number of ones$k$? Alternatively let$G$be a graph ... • 1,955 3 votes 0 answers 141 views ### If$\sf{E} = \sf{NE}$. Then$\sf{NP}-{P}$contains no sparse sets [closed] I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21. In its proof, they suppose$L$is some sparse language in$\sf{NP}$($||L^{=n}||&...
• 139
3k views

I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be ...
• 547
254 views

### Are all computational models of quantum computing equivalent?

So the question was inspired by a seminar which presented the following models of quantum computing: Quantum Computing with Photons Quantum Computing with Rydberg atoms Quantum Computing with trapped ...
• 706
85 views

### Is the traveling salesman problem still NP-hard if all edges need to be covered as well?

If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard? Given a graph G with non-negative edge weights, is there a circular walk in G ...
73 views

### How hard is deciding the existence of a polygonization with prescribed perimeter?

Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
339 views

171 views

### How to calculate complexity in a high dimensional space?

Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong. For a specific f(), I'm defining a term '...
314 views

### On the usage of Arora and Barak's main lemma in their proof of the PCP theorem

I am a mathematician working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in ...
192 views

### Reference for computing the rank of a matrix in polynomial time

In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
1k views

### Has parameterized complexity led to better algorithms?

I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
• 301
411 views

### Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$

I have a certain impossibility result that holds unless $\mathsf{NP} = \mathsf{QP}$. It seems quite likely that one could strengthen this to hold unless $\mathsf{NP} = \mathsf{P}$, which I would not ...
• 778
220 views

### Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?

Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$. For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
• 383
89 views

### Complexity of Encoding a Matroid Flow Problem in a Matrix

Context: Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$. We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
• 464