Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
5,284
questions
0
votes
0
answers
20
views
Color a a general graph with maximal degree $\Delta$ using $2^{O(\Delta)}$ colors within $\log^{*}n$ rounds
Consider the following algorithm $A$ to 6-color an rooted tree within $\log^{*}n$ rounds in a distributed system:
1: Assume that initially the nodes have IDs of size $\log(n)$ bits
2: The root is ...
- 305
1
vote
1
answer
44
views
Why do simple Logical Gates have an Irrational amount of Bits?
Suppose $2$ bits are used to encode a message, A and B.
If you know $A$ is $1$, you have one bit of information.
If you know $A\land B$ is $1$, you have two bits of information.
If you know $A\land B$...
- 13
0
votes
1
answer
32
views
On proving the uncomputability of Kolmogorov complexity by contradiction
I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry ...
- 163
2
votes
1
answer
282
views
Constructing equivalent (to a polynomial-time degree) decision problems from function problems
Let's say we're some function problem, $R \subseteq \Sigma^* \times \Sigma^*$, where $\Sigma = \{0, 1\}$ and some oracle $O_R$ that solves $R$.
Now, we're given some language, $L \subseteq \Sigma^*$ ...
- 265
1
vote
1
answer
76
views
Integrality gap and complexity classes
I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems?
In particular, is there a class of problems for which their integrality ...
- 127
0
votes
1
answer
26
views
is this lanuage or it' complement not Turing-recognisable
K = {<J, a, b, c> : J is a Java program, a, b, and c are integer variables declared in J, and throughout the execution of J, a never has the same value as b and a never has the same value as c}.
...
- 31
3
votes
3
answers
64
views
Can you enumerate the set of all words over a finite alphabet?
Can you enumerate the set of all words over a finite alphabet?
- 31
0
votes
2
answers
60
views
Can all NP-complete problems be reduced to NP?
I know that by definition, all NP problems can be reduced to NP-Complete problems. But does that also applies the other way around?
Can all NP-Complete be reduced to NP problems?
My understanding is ...
2
votes
0
answers
159
views
Can protein folding destroy cryptography?
They say that protein folding is an NP-hard problem, meaning that if we could figure out how any protein folds, we could solve any NP problem in polynomial time. However, doesn't this basically ...
- 87
1
vote
0
answers
38
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 13
0
votes
1
answer
34
views
If NP problems are decidable, and decidable is subset of turning recognizable which recognizer can understand them?
I think the best way to explain my question would be to have sextuple (regular, context-free,
Turing-recognisable, decidable, P, NP).were you fill out 1 for promblem which lies into that section, ...
- 31
1
vote
0
answers
25
views
Can someone please explain classes MA and AM (with an example)? What happens to AM in case of PH[2]=PSPACE?
I am trying to understand two player (prover-Merlin and verifier-Arthur) interactive proof complexity classes and had a few doubts.
As I understand, the classes $MA$ and $AM$ involve two players, ...
- 743
7
votes
1
answer
1k
views
What is the complexity of theorem proving?
I'm learning some computer science and mathematics by myself. I know that proving theorems in ZFC is undecidable in general, but, is there a formal way to express how complex it is? Is it as complex ...
0
votes
3
answers
84
views
If X is poly-time reducible to Y and X is in P, then Y is in P
The answer I found on the Internet is false. But my argument is that if I know that X is poly-time reducible to Y, which means I can use Y as a sub-routine to solve X, i.e., if I have a blackbox of Y ...
4
votes
0
answers
48
views
The Hidden Subgroup Problem under different mappings
The Hidden Subgroup Problem (HSP) is an extremely prevalent problem in quantum computation, especially for factorization in Shor’s algorithm.
The problem is stated
Given an oracle for some function, $...
- 41
1
vote
1
answer
18
views
What are the sizes of 'functions' and 'fields' in the context of input to a decision problem?
I can reduce 3-Sat to the following NP-Complete decision problem:
Let $S = ${0,1,...,s-1}, $D \subseteq S$ and $P$ be a multivariate polynomial in $n$ variables. Decide yes iff there exists $\vec x \...
1
vote
0
answers
22
views
Class of optimization problems whose decision versions are in P
NPO is defined to be the class of optimization problems whose decision versions are in NP.
I would like to get the complexity class of optimization problems whose decision versions are in P.
Is such ...
- 127
0
votes
0
answers
39
views
Hardness of the bin packing problem
I have been reading up on the bin packing problem. In the bin packing problem, we are given $n$ items with sizes $a_1,a_2,\dots, a_n$ such that
$$
1 > a_1 \geq a_2 \geq \dots \geq a_n > 0
$$
The ...
2
votes
2
answers
606
views
Is it NP-hard to decide the existence of n subsets picked from n lists of subsets the union of which contains at most s elements?
You are given $n$ lists. The $i$-th list contains $k_i$ subsets of $\{1, \ldots, m\}$. You are also given an integer $s$. You should decide whether it's possible to pick up exactly one element (that ...
0
votes
0
answers
29
views
Does $PP\subseteq BPP$ imply $PP\subseteq RP$?
Consequence of $\mathsf{NP\subseteq BPP}$ to $\mathsf{NP\subseteq ZPP}$? clarifies $NP\subseteq BPP\implies NP\subseteq RP$.
What about for $PP$? Does $PP\subseteq BPP$ imply $PP\subseteq RP$ and $PP\...
- 2,861
3
votes
0
answers
121
views
Is there a class for optimization problems with polynomial-time-computable bounds?
An optimization problem can be described by two functions $f$ and $g$, such that:
$f$ is a binary predicate representing the constraints: $f(x,y)$ is True if the output $y$ is feasible for the input $...
- 5,790
2
votes
1
answer
71
views
Finding maximum via sum oracle
Let $A$ be an array of real numbers with a unique maximum element, such that $size(A)=O(2^N)$. Assume that we have an oracle that can evaluate a sum over any subset of indices of $A$ in $O(1)$ time. ...
- 133
0
votes
1
answer
75
views
Understanding reductions and notation
I am currently working through Sipser's Introduction to the Theory of Computation. In chapter 5, he defines that a Language $A$ is mapping reducible to language $B$, written $A\leq_m B$ if there is a ...
- 1
0
votes
0
answers
44
views
Why are polynomials a natural measure for easiness of computational problems? [duplicate]
We understand the exponential function to constantly grow, which we consider bad for a problem. By constantly growing I mean the ratio
$\frac{f(n+1)}{f(n)}$
never tends to 1, where $f(n)$ is the ...
0
votes
1
answer
22
views
P/poly and dyadic oracle
If we let a language L in {0,1}* be dyadic if for each x in L, and each index i with xi = 1, i is a power of 2, then consider the class of languages recognized by a polynomial time oracle machine with ...
- 13
0
votes
0
answers
14
views
Relativizations/Oracles for the BPP and RP complexity classes
If we consider the complexity classes RP and BPP, then to show RPBPP = BPPRP my first thought is we need to use some kind of majority voting to amplify our success probabilities. The issue is I don't ...
- 13
0
votes
0
answers
57
views
Finding a Polynomial Time algorithm for the 3-SAT Problem
Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :
Ai = (xr $\lor$ xs $\lor$ xt)
where 1 $\le$ r,s,t $\le$n and ...
2
votes
1
answer
194
views
Is this path planning problem NP-complete?
Given N integers L1, L2, ... , Ln ,we have a robot that starts at (0,0) moves north on integer grid for L1 steps, then it either continues in its current direction or makes 90 degrees right turn then ...
- 4,417
0
votes
0
answers
14
views
Analogue of NP for oracle problems
I was just reading this question on the quantum computation stack exchange. It asks whether the HSP is in NP or not, and the answer notes that NP is a class of languages, not oracle problems.
The ...
- 265
0
votes
0
answers
33
views
Envy-Free Allocation is NP-Hard
If we consider the class fair division problem where we have a set of $n$-agents and a set $M$ of $m$-items, where each agent has a valuation function defined on the set of items $$v_i : 2^m \...
- 31
0
votes
1
answer
77
views
Showing there exists a polynomial-time algorithm for deciding the existence of a linear classifier
For this question I figure we need to define a system of linear inequalities which I thought could be something like this : a1x1 + a2x2 + ... + anxn ≥ b if (x1, x2, ..., xn) ∈ X
a1x1 + a2x2 + ... + ...
1
vote
0
answers
32
views
Is the HSP with the symmetric group exactly equivalent to the Graph Isomorphism problem?
It is well known that an algorithm to solve the Hidden Subgroup Problem (HSP) with the symmetric group can solve the Graph isomorphism problem.
But is this true in reverse? Will an algorithm for graph ...
- 265
0
votes
0
answers
31
views
vertex-deletion and edge-deletion parameters
Let $\mathcal{G}$ be a graph class. For any class $\mathcal{H}$, we know that the minimal number of vertices that has to be removed from $G\in \mathcal{H}$ such that we get a graph from $\mathcal{G}$ ...
- 267
1
vote
1
answer
298
views
Unions of PSPACE-comlete problems that are PSPACE-complete?
Let $A,B\subsetneq\Sigma^*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete?
In ...
0
votes
1
answer
37
views
Universal lower bound of the multi message problem
The multi message problem is:
Let there be an undirected graph $G = (V,E)$ with $n$ vertices, and let $r \in G$. The algorithm sends a message $M_i$ of size $\Omega(\log(n))$ to each vertex $v_i$ ...
- 305
0
votes
1
answer
97
views
System of equalities and inequalities is NP-hard using a reduction from 3COLORING
We are require to show that a problem where the input is a system of equalities and inequalities, each involving polynomials of degree at most 2 (with integer coefficients) in n real variables x1, x2,...
- 25
3
votes
0
answers
54
views
Is there such a thing as $coW[1]$-hardness?
I have a problem $\mathsf{A}$ and I would like to analyze its (parameterized) computational complexity.
I found a parameterized reduction from the complement of the independent set ($\mathsf{coIS}$) ...
- 31
0
votes
2
answers
36
views
How can a $P(n)$ run in polynomial time if it calls $R(m)$ which has exponential time
We have a procedure $P(n)$ that makes multiple calls to a procedure $Q(m)$, and runs in polynomial time in n. Unfortunately, a significant flaw was discovered in $Q(m)$, and it had to be replaced by $...
- 305
0
votes
0
answers
37
views
Is PrefixFreeNP=P?
I was given the following definition of a verifier:
Verifier $V$ is called $PrefixFree$ if for every $x,y$ such that $V(x,y)=1$, then for every $y'$ (which is not an empty string, $y'\ne\epsilon$) $V(...
0
votes
1
answer
47
views
Time bounded Kolmogorov complexity and one way functions
I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that ...
- 251
0
votes
0
answers
22
views
Kolmogorov Complexity: Is there a Program P which outputs Kolmogorov string K, P doesn't contain K and P is longer than K?
Given a binary string, K, with length N, and Kolmogorov Complexity N, is there a program P, of length M, and with Kolmogorov Complexity M such that:
P outputs K.
M >= N.
P does not contain K.
- 101
1
vote
1
answer
31
views
Can you transform 3sat (or equivalent) into another satisfiability problem that increases the ratio of solutions to non-solutions
Say I have f(x1,x2,x3,...) where the output is either 0 for all inputs (unsatisfiable) or a variable boolean output of 0 or 1 depending on the input (satisfiable). Let's not consider functions that ...
1
vote
2
answers
88
views
Prove that the language L = { <T> : T is a Turing machine that runs in polynomial time } is not Turing-recognizeable
By "$T$ runs in polynomial time", I mean that $T$ halts for every input of length $n$ in $O(n^k)$ steps for some $k$.
By Turing-recognizable, I mean that there exists a Turing machine that ...
- 125
4
votes
0
answers
38
views
Interactive proof for PSPACE-hard problems different from QBF
The celebrated proof that IP = PSPACE relies on an interactive proof for the QBF problem.
Is there any other "natural" interactive proof for a PSPACE-hard problem other than QBF?
(of course, ...
18
votes
4
answers
2k
views
Measuring time complexity in the length of the input v/s in the magnitude of the input
I know that formally the time compliexity of an algorithm is measured in the length of the input, which in binary would be the number of bits required to encode the input.
The problem that I have with ...
- 183
0
votes
0
answers
27
views
$BQP$ vs $NP$ in the unlikely scenario of $PH=PSPACE$
It is known that: ${\sf BQP} \subseteq {\sf PSPACE}$ and ${\sf PH} \subseteq {\sf PSPACE}$. If tomorrow its proven that ${\sf PH} = {\sf PSPACE}$ it would also imply ${\sf BQP} \subseteq {\sf PH}$.
...
- 743
1
vote
1
answer
27
views
Constrained precedence parsing
This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem?
The setup is as follows: we are given $n$ ...
- 531
0
votes
0
answers
41
views
How do Turing machines output $f(w)$ for $O(1)$ reductions?
When speaking about many-one Karp reductions, the definition is stated below:
$$
A \leq_P B \iff \exists f \colon \: \Sigma^* \mapsto \Gamma^* \: \text{such that} \: (w \in A \iff f(w) \in B)
$$
where ...
- 153
1
vote
2
answers
279
views
Can the optimization version of a problem be NP-hard while its decision version is in P?
I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-...
2
votes
1
answer
59
views
Is finding a Polytime reduction from $L_1$ to $L_2$ equivalent to proving $L_2 \in P \Rightarrow L_1 \in P$
I often hear NP-completeness as problems such that, if they were in $P$ all problems in $NP$ are in $P$. The true definition, though, is that NP-complete is a set of languages in NP that all languages ...
- 153