# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,735 questions
Filter by
Sorted by
Tagged with
28 views

### A $TM$ definition on approximation solutions to optimization problems

It looks like we are defining approximation solutions as a witness specifying program. We want to find a witness which agrees within some approximation of optimal. Is it possible to specify as '...
68 views

### On $\mu_p(BPP)$($p$-measure of $BPP$)

I was looking for a condition that would collapse all the way without $P=BPP$ if $RP$ is powerful. It was not clear $P=BPP$ could be proven in any formal ways as we know now if $NP=RP$ holds. To say ...
2k 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 ...
36 views

### Balanced and general $MAXkSAT$ known approximation results and bounds from $UGC$

$MAX2SAT$ has a $0.9401$ to $0.9402$ approximation algorithm which is conjectured to be optimal by $UGC$ while there is a balanced $MAX2SAT$ bound of $0.943$ approximation which is conjectured to be ...
63 views

### Verifier definition of NP/poly

I would like to know whether there is a definition of the class NP/poly in terms of (deterministic) polynomial time verifiers. The following is the definition of NP/poly I see everywhere (other than ...
34 views

183 views

### Why does Dinur's proof of the PCP theorem fail to work for unique games?

What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
46 views

### How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?

In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables. I would like to know, is there any algorithm that ...
43 views

135 views

### What does it mean by the statement: “a problem is hard to approximate ”?

In most of the research papers that I have read so far, I often come across the statement of the following form: "the problem is hard to approximate within any factor smaller than some constant&...
185 views

### Unambiguous Problems and Classes over Reals

Are there unambiguous analogues of $NP_{R}$ (using the BSS model, in all discussion)complete problems, and any results known about them? For instance, the canonical $NP_{R}$ complete problem $4FEAS$ (...
143 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 '...
216 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 ...
129 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, ...
335 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 ...
114 views

### Open problems/Conjunctures in non-uniform complexity if proved would imply P=NP

As we now, NP ⊈ P/poly would imply P≠NP. Can you mention some conjuncture/open problems in non-uniform complexity, that would imply P=NP,if proved
140 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 ...
79 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 ...
157 views

446 views

### Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis

In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “...
149 views

### What evidences are there that $PP$ is in $BQP$ and $PP$ is not in $BQP$?

Unlike hierarchy collapse arguments for classical complexity we have that quantum complexity is different. What evidences are there that $PP$ is in $BQP$? What evidences are there that $PP$ is not ...
43 views

### Non-rigid isomorphic structures

In many of the problems trying to solve hidden shift over some objects like graphs mainly the rigid classes are considered. For eg. in this and this isomorphism problem restricted over rigid graphs is ...
281 views

### 3SUM Complexity—A special(?) Case

In the paper “Consequences of Faster Alignment of Sequences” by Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of ...
152 views

### Why is it difficult for $GCT$ to prove super quadratic lower bound?

We have a quadratic lower bound for the Permanent versus Determinant problem. Why is it difficult for $GCT$ to improve it?
104 views

### Is mathematical proof itself NP-hard?

At the 8:00 mark of this video, he claims that proving things is itself an NP problem. I'm looking for more insight into this. Could someone help explain this concept to me and also provide a link to ...
110 views

### Can you diagnolize without mentioning simulation?

Are there any known diagonalization proofs, of a language not being in some complexity class, which do not explicitly mention simulation? The standard diagnolization argument goes: here is a list of ...