Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
4,442
questions
0
votes
1answer
19 views
Show that NL ⊆ P
Can somebody please explain this in simple terms. I don't understand Sniper's way to explain it.
He says this is a corollary to PATH is NL-complete which I do not understand either.
Can somebody ...
0
votes
0answers
22 views
Finding a kernel for 1-Bounded degree deletion of $O(k^2)$ vertices [duplicate]
In 1-BOUNDED DEGREE DELETION problem, we are given an undirected graph G and a positive integer $k$, and the task is to find at most $k$ such vertices whose removal decreases the maximum vertex degree ...
4
votes
1answer
170 views
Why does a polytime hitting set generator derandomize RP?
I am reading Goldreich, Vadhan, Wigderson: Simplified Derandomization of BPP Using a Hitting Set Generator and trying to understand the result that polytime hitting set generators (HSGs) would not ...
0
votes
0answers
50 views
Is the class $EP^{FewP}$ in $NP$ and $P^{UP}$?
https://complexityzoo.net/Complexity_Zoo:E#ep defines the class $EP$ as the set of problems solvable by an $NP$ machine such that if the answer is $NO$ all paths reject and the answer is $YES$ exactly ...
-2
votes
0answers
36 views
Is this solution for the Partition Problem right?
I've tried to solve the Partition Problem for 2 subsets minimizing the difference in the sum between the two subsets. I've coded the following:
...
0
votes
1answer
21 views
Showing that a problem in $NP$ admits two distinct verifiers that satisfy additional constraints
Show that any $S \in NP$ has 2 different polynomial-time verifiers $V_1, V_2$ such that, for all $x,y$, the following conditions hold:
If $V_1(x,y)=1$ then $V_2(x,y)=0$
If $V_2(x,y)=1$ then $V_1(x,y)=...
0
votes
1answer
23 views
Asymptotic notation for summations
I am struggling to understand why this property of asymptotic notation is true
2
votes
1answer
13 views
Padding a 2SAT clause
In http://web.mit.edu/neboat/www/6.046-fa09/rec8.pdf, I see that they pad a 2SAT clause $(x\vee y)$ to make it a 3SAT clause by writing $(x\vee y\vee p) \wedge (x\vee y\vee \neg p)$. Why doesn't $(x\...
2
votes
1answer
70 views
How does strong NP-completeness agree with encoding complexity?
I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
1
vote
2answers
25 views
Reduction from Independent Set with fixed vertex to Independent Set
I was looking to solve this reduction, but I dont see how to construct the new graph. It seems very simple but I'm not capable of do it.
I give you the complete explanation about this reduction.
We ...
2
votes
1answer
181 views
NOT satisfiable 3SAT instance certificate
Given a NOT satisfiable 3SAT instance, that we say $S$. Suppose that $M$ is a minimal subset of clauses of $S$ such that $M$ is NOT satisfiable. Say $X$ the subset of variables of $S$ that belong to ...
1
vote
1answer
31 views
Proof that a relation is in FP
How we can prove that the relation: $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^* \in FP$
I understand that we need to find a polytime algorithm to decide whether $(x,y) \in R$ since $(x,y)\in R=...
0
votes
1answer
24 views
Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?
I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes.
For example, if we didn't have a linear speed-up theorem, then ...
-2
votes
0answers
35 views
NP as the set of polynomial verifier and set of decidable problem in nondeterministic polynomial time
My initial idea is to show that the equality of the sets by first proving (a) ==> P is subset of NP and secondly, (b) <== NP is subset of P?
1
vote
1answer
71 views
Iterated multiplication of permutation matrices
Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where
$m=\mathit{poly}(n)$
$m=\...
2
votes
0answers
64 views
Prove lower bound on boolean circuit
Given matrix $A \in \{0,1\}^{n \times m}$ with $n$ rows and $m = 2^n - 1$ columns. Where $j$-th column is binary decomposition of $j$ ($j = 1 \dots 2^n - 1$). For example, if $n = 3$:
$ A = \begin{...
1
vote
2answers
33 views
What computational complexity classification does autonomous/self-driving cars belong to?
Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are ...
3
votes
1answer
31 views
Worst-Case Complexity of Quantifiers in Thompson's Construction
My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the ...
1
vote
1answer
118 views
Representing FP relations using witnesses
Let a relation $R$ be A-polynomial if there is a polynomial $p$ and a polytime algorithm $A$ such that for each $x$:
If $(x,y) \in R$ then there is a witness $w$ of length at most $p(|x|)$ such that $...
-2
votes
1answer
38 views
What is the relation between $USAT$, $UP$ and $NP=RP$?
Definition:
AtmostONESAT: SAT instance having promise of $\leq1$ witness.
What is the complexity consequence if an instance of $SAT\in$ AtmostONESAT can be decided whether or not there is a witness in ...
1
vote
1answer
49 views
Any problem in P can be reduced to the language of odd integers
Given $A=\left\{n\in \mathbb{N} \mid \text{$n$ is odd}\right\}$, we want to prove that if $S \in P$ then there is a Karp reduction from $S$ to $A$.
My attempt:
If $S \in P$ we can solve $S$ with a ...
13
votes
0answers
120 views
What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?
In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
1
vote
1answer
44 views
Prove/Disprove: NP is closed under “mixed” complexity
Let $\displaystyle S_{1} ,S_{2} \subseteq \{0,1\}^{*}$, we say $\displaystyle x\in S_{1}°S_{2}$ if it's of the form $\displaystyle x=x_{1} x_{2} ...x_{n}$, for $\displaystyle n$ even, such that:
$\...
0
votes
0answers
19 views
Are there more succint algorithm for translating NFA's to DFA's?
When translating an NFA to its deterministic equivalent, we get an exponential blowup due to the powerset construction method. I tried to search but couldn't find an appropriate question regarding ...
1
vote
1answer
83 views
Is the base of natural logarithms $e$ efficiently computable?
Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a ...
3
votes
1answer
38 views
Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$
The proof is in the image below, taken from "Quantum Computing Since Democritus":
Here's what I don't totally get: my understanding of random algorithms is that randomization is not done ...
0
votes
0answers
17 views
Polynomial reduction, #P-hard problems, and approximations
Consider two statements.
Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard.
Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error ...
2
votes
1answer
50 views
A data structure that supports efficient insertion of arbitrary integers, value lookup, and removal of all integers smaller than a given threshold?
I'm looking for a data structure that supports efficient:
Insertion of arbitrary integers.
Value lookup (given a particular value needle, return true if it's ...
1
vote
1answer
37 views
Randomized Version of NP
I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc.
Since the above classes are well-known, I will ...
0
votes
1answer
55 views
$coNP$ and $\oplus P$?
Let a non-deterministic machine have at most $2^{t+1}-1$ accepting paths (highest significant bit position is $t$ and lowest significant bit position is $1$).
I want to decide if the number of ...
0
votes
0answers
16 views
What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?
What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?
Could you, please, check my reasoning. Is it correct?
Here is my algorithm for ...
1
vote
1answer
18 views
What is uniformity in Boolean circuits exactly?
I have two questions on Kaveh's answer to Definition of uniform boolean circuit :
Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
0
votes
1answer
36 views
is advice function and an oracle the same thing?
In the context of P/poly complexity class, an advice function is mentioned.
How is the advice function different than an oracle(/certificate)?
https://en.wikipedia.org/wiki/Advice_(complexity)
https://...
0
votes
2answers
67 views
O(n+m) vs O(n+2m) time complexity
Are $O(n+m)$ and $O(n+2m)$ the same?
If $m>n$, then both complexities are $O(m)$. Likewise, if $n>m$, then they are $O(n)$. Is this correct?
2
votes
1answer
33 views
Two-color hitting set
Let $n,m$ be a positive integer with $m\ge 2n$. In the set $M=\{1,2,\dots,m\}$, some elements are black and others are white. Given $2n$ nonempty subsets of $M$, the task is to determine whether there ...
-1
votes
1answer
23 views
What is the generated grammar for this language?
I want to construct a regular grammar that generates words that contain both "ab" and "bc" as subwords with the alphabet of the terminal symbols {a,b,c}
My solution so far is
G=(Vn=...
0
votes
1answer
22 views
Give the Regular-Expression (NFA) with specific Separation Patterns
Question:
Given the RE (or NFA) for the set of all strings over $\Sigma ={a,b}$ such that: a occurs the odd number of times and each pair of a are separated by exactly $2n+2,n\geq 0$ b's.
Attempt:
...
-1
votes
0answers
36 views
NP-completeness of disjoint paths with bounded common nodes [duplicate]
Given an undirected graph $G=(V,E)$, $k$ distinct node pairs $(s_1, t_1), ..., (s_k, t_k)$ and an integer $\delta$, determine if there exist $k$ edge-disjoint paths from $s_i$ to $t_i$ $(1\leq i\leq k)...
2
votes
1answer
63 views
Sub-exponential time algorithm to compute playoff chances
There are 10 teams, Team A through Team J, playing in a triple round robin pool (each team plays thrice against each other team, for a total of a 27 games per team). After the round robin pool, the ...
0
votes
0answers
47 views
Which of the following statement is true?
Given two statement:
A:if inputs of a problem is online, then there is faster or equal
algorithm in view of time complexity for that problem when input is
offline.
B:if inputs of a problem is offline, ...
1
vote
1answer
36 views
A problem about asymptotic functions
Are there two function $f:N\rightarrow N$, and $g:N\rightarrow N$ such that $f(n)+g(n)\ne O(f(n))$ $\wedge$ $f(n)+g(n)\ne O(g(n))$?
My idea: i think because of for any $f:N\rightarrow N$, and $g:...
1
vote
1answer
55 views
Polynomial time verification of Graph Isomorphism problem
Using guess and check method, for two given graphs with the same number of nodes, a NTM selects a permutation of the node set and then checks if the edges are preserved.
The nondeterministic selection ...
0
votes
0answers
19 views
Length of PCP Proofs
Suppose a language $L$ has a non-adaptive PCP verifier which uses at most $r(n)$ random coins, and queries at most $q(n)$ locations of the proof, on inputs of length $n$. How can we show that there is ...
1
vote
2answers
61 views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
1
vote
0answers
91 views
Reduction between Parity-SAT and approximate counting
Consider two problems as defined here.
Approximate counting: Given a Boolean function $f(x)$, for $x \in \{0, 1\}^{n}$, distinguish between the two cases:
The number of satisfying assignments for $f(...
0
votes
0answers
53 views
Need help with a very specific Greedy Algorithm. Are there fast solutions?
i need help for a specific problem i have at work.
You have N number of rows in an array, each with some distribution of Numbers that range from 0 to N.Given an array of size 1000:
Row 1 might look ...
1
vote
1answer
34 views
What is the “formula” for “any chipher can be deciphered by a quantum computer”?
There are several quantum complexity classes in different ways analogous to NP: NQP, QMA, and, as I understand, others.
P=NP BPP=NP in simple words means "any cipher can be deciphered by a ...
2
votes
1answer
40 views
Is there a concept of probabilistic quantum computers?
Answering my question Yonatan N said a statement from which follows that there are computable functions of quantum time complexity strictly above polynomial.
Accordingly a Quora answer
Quantum ...
3
votes
1answer
60 views
Why do we use DAG rather than trees to represent search space of a search problem?
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on ...
2
votes
1answer
106 views
Efficient algorithm to compute the diameter of a convex set?
Is there a polynomial algorithm that can compute the diameter (the distance between the furthest points) of a convex set?
It is possible to do it efficiently for a set of points, but imagine that the ...
