Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

Filter by
Sorted by
Tagged with
4 votes
1 answer
107 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
A. G.'s user avatar
  • 43
0 votes
0 answers
50 views

Is checking at least $k$ solutions as hard as counting?

The problem of #SAT is "given a boolean formula $P$, count the number of solutions that satisfy this formula". As Wikipedia shows, #SAT is #P-complete. I'm thinking about a form of "at-...
staroperator's user avatar
3 votes
2 answers
77 views

Why is order/choice an issue for a logic for PTIME

As I'm reading on the question of a logic for PTIME and in particular about CPT and its variants, whilst things make sense and I follow along, I came to realise that I don't fundamentally understand ...
Matei Chesa's user avatar
3 votes
0 answers
82 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 ...
Marsh's user avatar
  • 31
0 votes
0 answers
76 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 ...
rock_lee's user avatar
0 votes
0 answers
42 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)$ ...
Turbo's user avatar
  • 12.9k
2 votes
0 answers
64 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))...
Turbo's user avatar
  • 12.9k
3 votes
0 answers
48 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 ...
Minsoo Kim's user avatar
3 votes
0 answers
60 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 ...
DiegoEmilio's user avatar
0 votes
0 answers
54 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 ...
apirogov's user avatar
  • 101
-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?
Turbo's user avatar
  • 12.9k
-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 ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
153 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, ...
Turbo's user avatar
  • 12.9k
-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$? ...
Turbo's user avatar
  • 12.9k
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\{...
Turbo's user avatar
  • 12.9k
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 ...
user11718766's user avatar
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 ...
Boran Erol's user avatar
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 ...
mti's user avatar
  • 117
-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 $|...
RT1's user avatar
  • 101
-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:\...
Thinklex's user avatar
4 votes
0 answers
142 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 ...
108_mk's user avatar
  • 225
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 ...
user2284570's user avatar
-3 votes
1 answer
150 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 ...
mti's user avatar
  • 117
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$ ...
user11718766's user avatar
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 ...
Demi's user avatar
  • 528
8 votes
0 answers
253 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.
domotorp's user avatar
  • 14k
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, ...
FooFighter39's user avatar
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 ...
TheoryQuest1's user avatar
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 ...
Mingda Qiao's user avatar
12 votes
2 answers
690 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 ...
Prafullkumar Tale's user avatar
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 ...
108_mk's user avatar
  • 225
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 ...
Hans Schmuber's user avatar
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:...
Dmytro Taranovsky's user avatar
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 ...
Daniel García's user avatar
2 votes
1 answer
121 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&...
Zach Hunter's user avatar
3 votes
1 answer
246 views

Complexity of determining whether the language of an P machine is empty

Suppose you are given a deterministic Turing machine and you are guaranteed it runs in polynomial time. What's the computational complexity of determining whether the language accepted by the machine ...
user1868607's user avatar
  • 1,017
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 ...
Tejas's user avatar
  • 137
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 ...
S. M.'s user avatar
  • 109
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 ...
S. M.'s user avatar
  • 109
6 votes
1 answer
429 views

Is relation between BQP and QMA resolved?

BQP vs QMA is a Quantum analogy of P vs NP. I recently went through the below pre-print on the IACR (International Association for Cryptologic Research) webpage. $BQP\neq QMA$ [link] I find it ...
108_mk's user avatar
  • 225
7 votes
0 answers
113 views

Parameterized complexity of factoring

When multiplying integer numbers $A$ and $B$, one can use a 0-1 matrix to represent one of the multiplication steps. For example, given numbers (written in binary) $A=1101$ and $B=1011$ the matrix is: ...
rus9384's user avatar
  • 355
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 ...
Heda Chen's user avatar
  • 181
0 votes
0 answers
32 views

What’s the difference between P-computable distributions and P-samplable distributions?

$\newcommand{\calC}{\mathcal{C}} \newcommand{\calD}{\mathcal{D}} \newcommand{\calE}{\mathcal{E}}$ I have two questions and the first one is presented in the title. The second one is about the ...
Heda Chen's user avatar
  • 181
2 votes
2 answers
77 views

State machine classes with sub-exponentially growing model spaces

State machines are useful tools for system modelling. They allow for a compact visual notation of discrete systems and provide a formal model of them. However, reasoning about the correctness of an ...
stateMachineOperator's user avatar
11 votes
1 answer
906 views

Status of András Faragó’s (second) claimed proof that NP=RP

In 2020, András Faragó claimed to have proved that NP = RP (discussion; v1 of the paper); the paper was later retracted due to a counterexample to theorem 1. A few days ago, Faragó posted another ...
Jiak Kantang's user avatar
12 votes
1 answer
466 views

Trade-off for Barrington's theorem

Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of ...
Michael Lampis's user avatar
3 votes
0 answers
89 views

What's the complexity of the "decision version" of counting the paths in a graph?

I learned that "counting the simple paths in a graph(whether directed or not)" is #P-Complete. I'm wondering what the complexity is for its decision version. Here are two types I'm ...
Wenhao Wu's user avatar
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 ...
Turbo's user avatar
  • 12.9k
1 vote
0 answers
68 views

Properties of #P functions that a GapP function may violate

I want to show a specific GapP problem is likely not in #P, actually very closely related to this question in terms of the area of mathematics it is from: How can I show a Gap-P problem is outside #P ...
Matt Samuel's user avatar
0 votes
0 answers
55 views

Implications of NL $\subseteq$ BQL/poly

As far as I could see it's not known whether NL $\subseteq$ BQL/poly. Is it actually not known? If not, what would be the implications of the inclusion?
eunice.goudarzi's user avatar

1
2 3 4 5
62