Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

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

Does there exist constant overhead reduction between common cryptographic primitives?

I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
Kagura Hitoha's user avatar
1 vote
0 answers
71 views

Consequences of a $Parity$ $P$-problem being reducible to a sparse language?

$Parity$ $P$ is the class where an $NP$-machine answers $YES$ if and only if the number of accepting paths of that turing machine is odd. With regards to the $P$ vs $NP$ question, there is a theorem ...
user avatar
7 votes
2 answers
1k views

Problems in NP with non-trivial certificate

For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I ...
Command Master's user avatar
10 votes
1 answer
300 views

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy? Couldn't find much in ...
J.Doe's user avatar
  • 468
0 votes
1 answer
123 views

Complexity of "opposite" version of a variant of #Positive-2-SAT

In this post ,I introduced a new variant of #Positive-2-SAT . This version of problem puts restrictions on the inputs of the #Positive-2-SAT such that we can only choose at max only 2 clauses from ...
Anuj's user avatar
  • 13
3 votes
0 answers
147 views

The $O(n^{1/r})$ upper bound of polynomial degree of OR over composite moduli

$\newcommand{\OR}{{\sf OR}} \newcommand{\MOD}{{\sf MOD}} $In the paper Representing Boolean functions as polynomials modulo composite numbers, Barrington, Beigel and Rudich showed that $\delta_m(\OR_n)...
Heda Chen's user avatar
  • 131
3 votes
0 answers
101 views

How do we show directly coNP is in MIP?

I know one can show that by $\mathsf{coNP}\subseteq\mathsf{NEXP}=\mathsf{MIP}$. But here I would like to start with a $\mathsf{coNP}$-complete problem and show there is a two-prover one-round ...
user50394's user avatar
  • 139
8 votes
1 answer
296 views

What is the general consensus on the NL vs P question?

As it stands, we know that NL is a subset of P, but we do not know if it is a proper subset or not. With that said, what is the general consensus? Do the majority think that NL = P or not? What would ...
Ashvin jagadeesan's user avatar
1 vote
1 answer
101 views

Explanation of Complexity class $S_2^P$?

I am trying to understand the complexity class $S_2^P$ defined as (https://en.wikipedia.org/wiki/S2P_(complexity)). A language L is in $S_2^P$ if there exists a polynomial-time predicate $P$ such that:...
J.Doe's user avatar
  • 468
10 votes
1 answer
805 views

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

Recently, I came across the problem of figuring out whether a given binary function $f(x)$ is constant (0 for all values of $x$ or 1 for all values of $x$) or balanced (0 for half of values and 1 for ...
Thiago's user avatar
  • 119
2 votes
1 answer
90 views

Fine-grained average-case derandomization

Many believe derandomization with polynomial overhead, $\mathsf{P} = \mathsf{BPP}$, because it follows from $2^{\Omega(n)}$ circuit lower bounds for $\mathsf{E}$ (IW97). Do we have any evidence for or ...
Nicholas Brandt's user avatar
3 votes
1 answer
198 views

Priority queue implementation with both find-min and delete-min $o(\log n)$

Question: There are several priority queue implementations listed on Wikipedia, along with amortized complexities of each of their basic operations: Does anyone know of an implementation in which the ...
Franklin Pezzuti Dyer's user avatar
1 vote
0 answers
48 views

Oracle for the permanent-of-gaussians problem

In this paper, Aaronson and Arkhipov formulate the $GPE_\times$ problem as follows: given an $n \times n$ matrix $X$ of i.i.d. Gaussian random numbers, find the permanent of $X$ up to multiplicative ...
Alexey Uvarov's user avatar
7 votes
0 answers
171 views

Baker–Gill–Solovay Theorem: why $2^n/10$ steps?

Context I'm teaching an introductory complexity theory course right now and although I work in adjacent areas, I'm not an expert on complexity theory myself, so I'm still in the process of working ...
Manuel Eberl's user avatar
3 votes
1 answer
224 views

Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

It is known that the problem of integer linear programming is NP-hard, but its fractional relaxation can be solved in polynomial time. The concept of fractional relaxation can be applied to any ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
85 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 ...
Turbo's user avatar
  • 12.8k
2 votes
1 answer
116 views

Perm and Det mod $2^k$ - I

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 ...
Turbo's user avatar
  • 12.8k
2 votes
0 answers
77 views

Variants of complexity classes that allow "adversarial inputs"?

Wikipedia defines BPP as follows: Alternatively, BPP can be defined using only deterministic Turing machines. A language L is in BPP if and only if there exists a polynomial p and deterministic ...
Jason Gross's user avatar
4 votes
0 answers
250 views

Permutation generation problem using swaps

This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input. We're given as input ...
Mohammad Al-Turkistany's user avatar
0 votes
0 answers
35 views

Is SZK dependent on the verifier’s model of computation?

What if instead of a probabilistic TM, the verifier in the definition of SZK was a quantum TM? How would this affect its relation to other classes? Would Statistical Difference still be a complete ...
Irna Mosa's user avatar
0 votes
1 answer
74 views

Exchange cards with sum requirement

Given are positive integers $a_1,\dots,a_{2k},b_1,\dots,b_{2k},S$ such that $\sum_{i=1}^ka_i = \sum_{i=k+1}^{2k}a_i = S$ and $\sum_{i=1}^kb_i = \sum_{i=k+1}^{2k}b_i = S$. There are $2k$ cards, card $i$...
TZM's user avatar
  • 123
2 votes
0 answers
65 views

Open Quantum Analogs to Classical Problems

I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
SAS's user avatar
  • 121
2 votes
1 answer
211 views

Examples for Real-time vs Linear time

A real-time Turing machine (with multiple tapes) runs in linear time. It is known [1] that there are languages recognizable in linear time by a multitape Turing machine but not recognizable in real-...
QMath's user avatar
  • 303
0 votes
0 answers
48 views

Complexity of XOR-Knapsack

Edit: Actually I should have been more careful. Maybe the optimal way to solve this is to approach it as a series of $k'-$XOR sum problems (Generalized birthday due to Wagner) for increasing $k'.$ And ...
kodlu's user avatar
  • 2,070
0 votes
0 answers
49 views

Reduction of Monotone-1-in-3-SAT to Cubic-Monotone-1-in-3-SAT

3-SAT is an NP-Complete problem. Now given a 3-SAT instance it can be transformed to a Monotone-1-in-3 SAT instance thus even Monotone-1-in-3-SAT is NP-Complete (am aware of this reduction). But, as I ...
J.Doe's user avatar
  • 468
0 votes
1 answer
322 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 ...
Loic Stoic's user avatar
6 votes
0 answers
154 views

Consequences of $P^{NP[o(n)]} = P^{NP}$

I am wondering what the consequences of $\text{P}^{\text{NP}[o(n)]} = \text{P}^{\text{NP}}$ are. Does this imply the collapse of the polynomial hierarchy or contradict something like $\text{ETH}$? I ...
user68775's user avatar
11 votes
12 answers
5k views

Theoretical Computer Science vs other Sciences?

So I‘m in my fifth semester studying Computer Science at a German university, so I‘ve only scratched the surface of Theoretical Computer Science, namely Logic, Formal Languages, Automata Theory, ...
voltas1231's user avatar
4 votes
2 answers
193 views

NP-hardness: (planar) directed feedback vertex set problem with bounded degree

My question is the directed version of this one. (I know the results and proofs about feedback vertex set in undirected graphs or undirected planar graphs; so I am concern about the directed feedback ...
Blanco's user avatar
  • 421
3 votes
0 answers
99 views

$\mathsf{coNP}^{\mathsf{\#P}}$ and $\mathsf{coNP}^{\mathsf{\#P}^\mathsf{\#P}}$

I was reading a paper that demonstrates that deciding whether a loop-free program is $\varepsilon$-differentially private is $\mathsf{coNP}^{\mathsf{\#P}}$-complete. What are some other problems that ...
Glycerius's user avatar
  • 131
5 votes
0 answers
113 views

How is inapproximability by polynomial size circuits sufficient for the Nisan-Wigderson generator?

I couldn't understand how exactly Yao's XOR lemma was used to prove the following claim made in the proof of Theorem 2 of the original paper describing the Nisan-Wigderson generator, so I decided to ...
Johnny's user avatar
  • 201
0 votes
1 answer
139 views

Sources that prove solving 2-SAT with DP takes linear time

Would anyone have any sources that describe/an explanation of how solving 2-SAT using dynamic programming takes a linear amount of time? Can't seem to find a text that proves it in detail/formality. ...
wtfamidoing's user avatar
3 votes
0 answers
99 views

Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?

Given are a prime number $p$ and a parameter $s\in\mathbb{N}$. What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
user avatar
3 votes
1 answer
90 views

END OF THE LINE problem finding a node with in-degree $0$ or out-degree $0$ depending on the initial node

The END OF THE LINE problem is stated as Given two circuits, P and N, a node, v, is balanced if $P(N(v)) = N(P(v)) = v$ or $P(N(v)) \neq N(P(v)) \neq v$. Given that $0^n$ is not balanced, find ...
wavosa's user avatar
  • 135
5 votes
2 answers
178 views

Lower bound for sorting without using a decision tree model

Can we prove the lower bound for the sorting problem just by Turing machine model? It seems that available proof of sorting is based on the assumption that the algorithm only uses comparison so we can ...
Hao Huang's user avatar
4 votes
1 answer
109 views

NC0 randomnes vs. non-uniformity

In Ajtai and Ben-Or. A theorem on probabilistic constant depth Computations. STOC '84, 1984 Ajtai and Ben-Or show a non-uniform derandomization of BPAC0. Is there a similar relation known for ...
user68538's user avatar
0 votes
1 answer
152 views

What is the simplest one-way function (in terms of boolean circuit complexity)?

What is the simplest known one-way function? By simplest, I mean, when implemented as boolean logic, the number of AND/OR/NOT gates needed is minimal (smallest circuit complexity). (I'm trying to find ...
Azuresonance's user avatar
8 votes
1 answer
230 views

Is it $NP$-hard to check whether a given algebraic circuit computes permanent?

Given are a natural number $n\in\mathbb{N}$ and a polynomial $P$ in the form of an arithmetic circuit $C$ over $\mathbb{Z}$ (a circuit which only uses $+$ and $\times$ gates and integer constants as ...
user avatar
7 votes
0 answers
113 views

Complexity of the unique homomorphism problem up to automorphisms

I am interested in the following problem: given two relational structures $\mathbf{A},\mathbf{B}$, is there a unique homomorphism from $\mathbf{A}$ to $\mathbf{B}$ up to automorphisms of $\mathbf{B}$, ...
Rémi's user avatar
  • 143
1 vote
0 answers
335 views

Claimed proof of PSPACE ⊆ BQP on arXiv

A new paper appeared on arxiv: PSPACE ⊆ BQP by Shibdas Roy: https://arxiv.org/abs/2301.10557 From the abstract: The complexity class PSPACE includes all computational problems that can be solved by a ...
kodlu's user avatar
  • 2,070
4 votes
0 answers
106 views

$\mathsf{NL}$ vs. $\mathsf{AC}^1$

It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$). Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
Alexey Milovanov's user avatar
2 votes
0 answers
59 views

hardness of partition of permutation into a minimum number of monotone subsequences

Given a permutation P, a monotone subsequence is a subsequence (i.e. the elements do not have to be consecutive in P) that increases or decreases. This leads naturally to the following optimization ...
steven kelk's user avatar
2 votes
1 answer
421 views

Are regular expressions inherently more difficult to construct than DFAs for humans?

When I am asked to construct a regular expression and DFA that would accept a language $L$, I usually find it much easier to construct the DFA (almost coming mechanically for me) than it is to ...
user3508551's user avatar
  • 1,088
3 votes
2 answers
118 views

Encoding of finite automata in Intersection Non-Emptiness problem

The intersection non-emptiness problem is defined as follows: Given a list of deterministic finite automata as input, the goal is to determine whether or not their associated regular languages have a ...
user1868607's user avatar
3 votes
1 answer
248 views

Is modular square roots modulo primes in $NC$?

Assume modulus is prime. Is modular square roots then in $NC$? If not then, are there special primes or prime powers or numbers related to these (such as $2^k\pm i$ where $i\in\{-1,0,+1\}$) where it ...
Turbo's user avatar
  • 12.8k
0 votes
1 answer
67 views

Require Hamming weight in CNF

I have a SAT problem in conjunctive normal form that I’d like to solve, but I need to add one more condition: for the existing variables $x_1,\ldots,x_n$ the Hamming weight is $k$. (It would be ok to ...
Charles's user avatar
  • 1,737
0 votes
0 answers
56 views

Restrictions on set of infinitely many n's for which an algorithm breaks distributional hardness

Say we want to capture the notion that an efficiently samplable distribution $D(1^n)$ is hard with respect to some boolean function $f$ for a decision problem or some efficient relation $R$ for a ...
Nathan's user avatar
  • 117
1 vote
0 answers
89 views

Is complexity class containment preserved relative to any oracle?

That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
abelard-to-girard's user avatar
0 votes
0 answers
95 views

How to prove that a given class of convex programs cannot be solved by linear programming?

Given the following program, where $f, g$ are convex functions: $$ \text{minimize}~~ f(x) \\ \text{subject to}~~ g(x)\leq 0 $$ the problem can be solved by convex programming algorithms, but it would ...
Erel Segal-Halevi's user avatar
2 votes
1 answer
136 views

Counting argument for LTF circuits

In Boolean circuit complexity, Shanon's counting argument shows that a random Boolean function on $n$-input bits requires a circuit of size $\Omega(2^n/n)$ to be computed by a circuit made of AND, OR ...
Tulasi's user avatar
  • 327

1
2
3 4 5
61