Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
0 votes
0 answers
70 views

Proof of coNE ⊆ NE/poly

I'm finding it hard proving that NE/poly contains coNE which is backed by Complexity Zoo. It states that we can use the proof for NEXP/poly containing coNEXP but the link to the reference paper ...
3 votes
0 answers
69 views

Where is $\mathsf{BPP^{NP}}$ in the polynomial hierarchy?

We know that $\mathsf{BPP}$ is in $\mathsf{\Sigma^P_2\cap \Pi^P_2}$ by Sipser-Lautemann, as this proof relativizes we can get $\mathsf{BPP^{NP} \subseteq \Sigma^P_3\cap \Pi^P_3}$, but are there any ...
6 votes
1 answer
462 views

Bijection between NP-complete problems

If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?
1 vote
0 answers
173 views

Perm and Det mod $2^k$ - II

Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
5 votes
3 answers
15k views

what is the real difference between traveling salesman problem (TSP) and vehicle routing problem (VRP)?

Both problems are well-known NP-hard problems with great similarities. In fact, I do not see the real difference between these two problems. It seems relatively easy to model TSP in the form of VRP ...
0 votes
0 answers
41 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
8 votes
1 answer
216 views

deciding $\beta$-equality of planar lambda terms

Mairson showed that the problem of computing the $\beta$-normal form of a linear lambda term (or equivalently, computing its principal type) is complete for polynomial time. Harry Mairson. Linear ...
2 votes
0 answers
63 views

On mod $p$ constructions related to determinant

Given an $m\times m$ matrix $M\in\mathbb Z^{m\times m}$ and a prime $p$, is it possible to construct in $Logspace$ another matrix $t_1(M)$ whose determinant is guaranteed to be determinant $Det(t_1(M))...
3 votes
0 answers
47 views

Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
0 votes
0 answers
88 views

On mod $2^i$ $+$-reducibility of permanent

Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$. Is ...
3 votes
0 answers
59 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
0 votes
0 answers
53 views

Why can't we just reduce from Bounded HALT to Bounded PCP?

We know that: PCP is famously undecidable (as it can encode any DTM), but Bounded-HALT (DTM on some input halts in at most k steps) is EXPTIME-complete, and Bounded-PCP (there is a matching ...
-1 votes
0 answers
54 views

NTM preserving modular number of accepting paths

Given a prime $p$ and an NTM with number of accepting paths $g$, is it possible to construct an NTM with number of accepting paths $g\bmod p$ in polynomial time where by $g\bmod p$ I mean the ...
-2 votes
0 answers
52 views

Graph theoretic problems complete for certain counting classes

What are some graph theoretic problems complete for SpanL, TotL, OptL classes? SpanP, TotP, OptP classes?
1 vote
0 answers
152 views

Relation between $k$-sum failure and $P=NP$

If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails? In particular, ...
-2 votes
0 answers
35 views

NP vs QuasiP and W[1] vs FPT

If $F[1]=WPT$ then ETH is false. The converse is unknown (https://en.wikipedia.org/wiki/Exponential_time_hypothesis#Structural_complexity). How about the strong assumption of $NP\subseteq QuasiP$? ...
0 votes
0 answers
56 views

Complexity of LSB and MSB of Diffie-Hellman

Given generator $g$ of multiplicative cyclic group modulo $p$ a prime and two elements $h_1$ and $h_2$ such that there are $x_1$ and $x_2$ respectively satisfying $g^{x_i}=h_i\bmod p$ at every $i\in\{...
1 vote
0 answers
64 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
0 votes
0 answers
65 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...
2 votes
0 answers
102 views

Constructing complex languages without "recursion"

I'm curious of the ways we can construct provably complex languages. In particular, most constructions (i.e., the one used for proving the Time hierarchy theorem) seem to rely on encodings of Turing ...
-2 votes
0 answers
163 views

Why do we belive that P = BPP?

My teacher said that this is what most of the reaserchers belives and it seems wierd to me. I know that after amplification the vast majority of random r's will be sufficiont for all x i.e. for all $|...
-1 votes
1 answer
47 views

Computability/Complexity of optimization problems in general

Dear StackExchange community, I have a question, or better phrased I am confused and would like to be enlightened by you! So assume we have a (optimization) problem like that: Instance: Let $f:\...
4 votes
0 answers
141 views

Is there a 'mathematical program' to separate P from BQP?

This question has been motivated by the existence of an ongoing (and possibly long-term) program for $P\neq NP$ conjecture like GCT(Mulmuley, 1999). Usually, such programs are marked by long and ...
-3 votes
1 answer
148 views

The most complex language? [closed]

I'm interested in understanding the complexity of languages. If I wanted to construct a language that is very difficult to decide, how would I go about this? Is it known whether we can artificially ...
1 vote
0 answers
76 views

What would be the cost to factor a 1024‒bits RSA modulus most economically within months today?

Of course this is a question with an answer that is due to evolve. A 2002 paper about TWIRL stated that the cost would be around 10M$$ and an other 10M$ to manufacture the devices. A later 2007 paper ...
11 votes
1 answer
523 views

Connection between PCP and L=SL

The book by Arora and Barak contains in chapter notes on PCP We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's ...
8 votes
1 answer
409 views

Resource-bounded variant of Kolmogorov complexity

Consider the variant of Kolmogorov complexity, where the program is only allowed to use a bounded amount of resources. This more closely resembles the practical situation, where decompression needs ...
7 votes
0 answers
94 views

Original formulation of Spira's Lemma

I'm currently reading the book "Proof Complexity" by Jan Krajíček (2019), where Spira's Lemma is mentioned: Let $T$ be a finite $k$-ary tree and $|T| > 1$. Then there is a node $a \in T$ ...
5 votes
1 answer
113 views

How to intuitively express the hardness of Minicrypt and Cryptomania?

My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say Algorithmica means “NP is easy”, Heuristica means “NP is hard on worst-case but easy on ...
9 votes
3 answers
306 views

Cheap online selection with weighted comparisons

Suppose we want to find the smallest element of a set $S$, whose elements are indexed from $1$ to $n$. We do not have access to the values of these elements, but we can compare any two elements of $S$...
1 vote
0 answers
99 views

Why does the Time Hierarchy Theorem fail relative to promise problems?

Define Program Evaluation (PE) to be the promise problem of determining whether a program (written in a Turing-complete language) returns True or False. The promise is that the program will return ...
8 votes
0 answers
252 views

Is GCT still active?

Is Mulmuley's geometric complexity theory program still active? I tried to look it up online, and I haven't seen anything from the last couple of years.
15 votes
2 answers
1k views

Law of the Excluded Middle in complexity theory

A recent blog post by Lance Fortnow discusses non-constructive proofs, where "non-constructive" here means that the law of the excluded middle is used in a substantive way. That is, one ...
2 votes
1 answer
188 views

Research masters programs in theoretical computer science (with a focus on complexity theory)

I am in my 2nd year of my Computer Science degree. I am deeply interested in Complexity Theory, and I plan to pursue a career in this field I am from South Asia, and research here is not up to par, ...
12 votes
2 answers
689 views

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Do we know any problem that satisfies the following criteria? It is polynomial-time solvable on trees. It is NP-complete when restricted to graphs of treewidth 2. The problem can be encoded only ...
0 votes
0 answers
36 views

converting K-SAT clause to a p-in-L-SAT equation

Given a generic K-SAT instance $S$ with $n$ boolean variables. Is it possible to convert a clause of this instance into an equivalent p-in-L SAT system of equations such that the number of new clauses ...
4 votes
0 answers
74 views

Uniform lower bounds in terms of the matrix multiplication exponent $\omega$?

Let $f(n)$ denote the minimum number of arithmetic operations needed for multiplying two $n\times n$ matrices, and $\omega = \inf\{p \ge 0: f(n) = O(n^p)\}$ be the matrix multiplication exponent. Is ...
0 votes
0 answers
83 views

Is there a Hidden subgroup problem in BQP but suspected not to be in NP?

Wikipedia lists HSP problems in abelian and non-abelian groups. So does the following (extensive) compedium. I searched and found none is a BQP-complete (or even BQP-hard) problem. There has been a ...
1 vote
0 answers
472 views

Is it known that P $\neq$ NP implies BQP $\neq$ NP?

Pretty much the title. Is there any result that shows that $P \neq NP \Rightarrow BQP \neq NP$. I think it's pretty clear that $BQP \neq NP \Rightarrow P \neq NP$, as $P$ is a subclass of $BQP$. But ...
1 vote
0 answers
64 views

Is there a succinct representation of factoring which remains computationally intractable?

I'm looking for a succinct version of the factoring problem: i.e. given integers N and k, does N have a prime factor less than k, but somehow the input takes exponentially fewer bits to input? Ideally ...
16 votes
3 answers
4k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
5 votes
1 answer
338 views

How does one "understand" complexity theory?

There's a famous quote by Bob Thomason about Grothendieck that he tried to understand algebraic geometry whilst everyone else was super-fixated on trying to prove theorems. Complexity theory, as one ...
17 votes
4 answers
1k views

How can I show a Gap-P problem is outside #P

There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take ...
25 votes
2 answers
2k views

Is finding Logspace reductions harder than P reductions?

Motivated by Shor's answer related to different notions of NP-completeness, I am looking for a problem that is NP-complete under P reductions but not known to be NP-complete under Logspace reductions (...
0 votes
0 answers
60 views

Undecidability of games with limited hidden state

Surprisingly, approximate win probability for one-player games with randomness and 3 bits of hidden state (in addition to non-hidden state; rational transition probabilities) is uncomputable. Question:...
2 votes
0 answers
79 views

On The Complexity of Block-Interchange Distance for Binary Strings

The block-interchange distance problem is defined as finding the minimal number of subsequences swaps to apply to an input string to turn it into a desired string. It is a well studied tractable ...
1 vote
1 answer
321 views

Sparsification and critical clauses in SAT

I have been studying the Exponential-Time Hypothesis, ETH, from this paper, there defined $s_k = \inf\{\delta \geq 0 | k\text{-}SAT \in RTIME[2^{\delta n}]\}$. But in that paper's page number 10, I ...
16 votes
3 answers
6k views

Circuit complexity of Majority function

Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I ...
3 votes
1 answer
226 views

Operation on Sub-exponential Reduction

I have a question concerning the SERF-reducibility of Impagliazzo, Paturi and Zane and subexponential algorithms. My question is: is a composition of two SERF reductions a SERF reduction? Are there a ...
2 votes
1 answer
120 views

Approaches to fast matrix multiplication and their limits

Let $\omega$ be the smallest constant so that we can do matrix multiplication in complexity $n^{\omega+o(1)}$. I am wondering what are the known avenues which establish the non-trivial bound $\omega&...

1
2 3 4 5
62