All Questions
Tagged with complexity or complexity-theory
5,612 questions
1
vote
2
answers
272
views
Boolean circuits with fan-out of each gate is 2
I am following the book of Arora and Barak book.
We consider Boolean circuits as we do, Specifically, inner nodes are either AND, OR (both – fan-in 2), or NOT (fan-in 1) gates. The fan-out of each ...
0
votes
1
answer
44
views
Are problems with an arbitrarily large search space in NP?
Let's say I have a problem with some input x. Each input x induces some arbitrarily large (but finite) search space. To make this more concrete, let's say a set of size proportional to 2^2^2^|x|. For ...
2
votes
1
answer
228
views
A 2-coloring of a bipartite graph such that one of the partitions contains exactly k vertices
Given the efficient solvability of the $2$-coloring problem in bipartite graphs, I claim that the this problem can be accomplished within polynomial time.
A algorithm for solving this problem involves ...
0
votes
0
answers
43
views
Is checking GCD in NC or strongly P?
Given two integers $m$ and $n$ computing $\mathsf{GCD}(m,n)$ is not known to be either in $NC$ or in strongly Polynomial time.
Given three integers $m$, $n$ and $g$, is testing $g=\mathsf{GCD}(m,n)$ ...
1
vote
0
answers
40
views
Can we construct the circular permutation from partial partitions?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
0
votes
1
answer
97
views
$f$ is Reduction from $\texttt{INDSET}$ to itself
My teacher said in his lecture( followed by the book Barak and Arora) the following:
We will imagine that a shocking discovery reveals that there exists a function $f$, thinking in linear time, so ...
0
votes
1
answer
67
views
Is it possible there exists a reduction that satisfies conditions of reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}?$
I am following the Barak and Arora book. I have asked this question regarding reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}.$
Is it possible to show that there exists a reduction that satisfies ...
1
vote
1
answer
70
views
Reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$
I am following the Barak and Arora book, in circuit chapter, they use direct reduction from $\texttt{CKT-SAT}$ to $\texttt{3SAT}$ directly without any clue.
How to construct an explicit reduction ...
0
votes
0
answers
48
views
Encapsulated linear memory of Turing Machine
A function $f$ is said to be thinking in an encapsulated linear memory if:
$f(x)$ is a polynomial block (that is, there exists a polynomial $q$ so that $|f(x)|\leq q(|x|)$) for each input $x$.
...
3
votes
0
answers
63
views
Approximation algorithm to estimate diameter of points in metric space
Given an arbitrary metric space $M=(X,d)$, is there a $(1+\epsilon)$-approximate algorithm (maybe probabilistic or randomized) that can estimate the diameter of $X$? This algorithm should be faster ...
1
vote
0
answers
30
views
Modifying Counting Sort for in place sorting
I'm interested in the following problem from CLRS (Problem 8-2 e)
Suppose that the n records have keys in the range from 1 to k. Show how to modify counting sort so that it sorts the records in place ...
4
votes
1
answer
51
views
Citation/ Proof of a theorem in computational complexity about recursive majority
Circuit Depth Lower Bound for Iterated Majority Function
Let $k \geq 3$ be a fixed integer. The function computed by a balanced $k$-ary tree of depth $d(n) = \Theta(\log n)$, where each node computes ...
0
votes
0
answers
33
views
Can Shannon Entropy Be Used to Refine Bounds on Kolmogorov Complexity?
I am new in this field but as I understand Kolmogorov complexity is non-computable, but the Shannon entropy is computable.
The definition of Shannon entropy is:
$${\displaystyle \mathrm {H} (X):=-\sum ...
0
votes
0
answers
108
views
Turing machine that makes exactly $2^{|x|}$ steps on any input $x$
I have the following problem:
Construct a Turing-machine that makes exactly $2^{|x|}$ steps on any input $x$. The machine can have $k$ tapes but only a fixed number of states (thus, the number of ...
0
votes
1
answer
138
views
Nondeterministically guess cycle in graph
In the following G is directed graph and circuits are not necessarily simple.
$$\text{2CIRC}_{1/2} =
\left\{\langle G=(V, E) \rangle : G \text{ contains two or more cycles of length }\frac{|V|}{2}\...
1
vote
1
answer
48
views
Largest subset of $RE$ whose automata are decidable
Recall that the Chomsky hierarchy that says regular languages correspond to (non)deterministic finite-state machines, context-free languages correspond to non-deterministic pushdown automata, and ...
2
votes
1
answer
180
views
Polynomial time reductions in DTIME
A class $∁$ is closed under polynomial time reductions if for every two languages $L_1, L_2$
such that $L_1 \leq_p L_2$ and $L_2 \in ∁$, it holds that $L_1 \in ∁.$
How to Show that for every $𝐿_1 ∈ \...
1
vote
1
answer
77
views
If $𝐵 ∈ \text{PSPACE},$ then $𝐴 ∈ \text{PSPACE}.$
We say that a language $𝐴$ has a probabilistic-poly-time reduction $𝑓$ to a language $𝐵$ if:
There exists a probabilistic polynomial time TM computing the (randomized) function $𝑓.$ Note that $𝑀(...
3
votes
3
answers
120
views
Can the time complexity of verifying a solution ever be greater than the complexity of the solution
I can not find an example problem space where the complexity (time) of verifying the solution is greater than that of solving the problem.
But I was hoping there would be a formal proof of this out ...
1
vote
1
answer
36
views
self-reducible in NP-time
We say that a language 𝐿 is 𝑘-self-reducible if there exists a function 𝑓 such that:
𝑓 is computable in polynomial time, and
There exists $𝑛_0 ∈ ℕ$ such that for all 𝑥 of length at least $𝑛_0$...
1
vote
0
answers
49
views
Data structure for tracking boolean clauses size
Given an unordered sequence of n boolean conjonction clauses which may contain duplicates, I am looking for a data structure that would track the number of clauses grouped by the number of variables ...
2
votes
1
answer
47
views
PSPACE, probabilistic-poly-time reduction
A language $𝐿$ is in the class BPP if there exists a probabilistic polynomial-
time TM, denoted N, such that: for every $𝛼 ∈ \{0,1\}^∗:$
$$𝛼 ∈ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ≥
2
/3\\
𝛼 ∉ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ...
1
vote
1
answer
34
views
BPP, probabilistic-poly-time reduction
A language $𝐿$ is in the class BPP if there exists a probabilistic polynomial-
time TM, denoted N, such that: for every $𝛼 ∈ \{0,1\}^∗:$
$$𝛼 ∈ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ≥
2
/3\\
𝛼 ∉ 𝐿 ⇒ Pr[𝑁(𝛼) = 1] ...
2
votes
1
answer
60
views
self reducible in p-time
We say that a language 𝐿 is 𝑘-self-reducible if there exists a function 𝑓 such that:
𝑓 is computable in polynomial time, and
There exists $𝑛_0 ∈ ℕ$ such that for all 𝑥 of length at least $𝑛_0$...
1
vote
0
answers
25
views
How long will algorithm dealing with combinations take to compute
I have a set of 1000 items and want to go through all subsets of size 499 of these elements.
In python library I will use “yield” function so I generate the sets rather than cause overflow, but I am ...
2
votes
1
answer
70
views
Understanding the concept of "co-": is it really a complement?
I don't quite understand the concept of complement in complexity theory. I don't understand the connection between this concept of complement and the complement from set theory. As the Wikipedia ...
1
vote
0
answers
32
views
Depth of circuit computing f(x) = "first n bit string with circuit complexity sqrt(n)"
I want to construct a depth $\mathrm{poly}(n)$ circuit computing $$f(x) = \text{first }n\text{ bit string with circuit complexity }\sqrt n$$ where $x \in \{0, 1\}^n$. I see how to do it with depth $2^...
1
vote
1
answer
55
views
Is the difference between an unrecognizable language and a finite language decidable? recognizable?
Given 2 languages, A and B, such that A is not turing recognizable, B is finite, is it true that A-B is necessarily not turing recognizable?
I am studying to an exam and would appreciate your help! I ...
3
votes
1
answer
77
views
When is an algorithm "equal" to another?
I have two algorithms $P, Q$ for solving the same problem (a decision problem on sequences in $R^n$) and I want to decide if they differ in any meaningful way. The following describes the constraints:
...
0
votes
1
answer
38
views
Complexity of Scheduling n Tasks on m Machines with Identical Execution Times, Dependencies, and Time Lags
This is a scheduling problem with $n$ tasks across $m$ machines. Tasks have dependencies (DAG) and can be divided into two types: A) need resources $R$ and have an identical execution time. B) do not ...
-1
votes
2
answers
172
views
Will this proof method work for p vs np
Given, that NP is the class of all problems that a non-deterministic Turing machine can solve in polynomial time, and proving P = NP will prove that there is no difference between a non-deterministic ...
1
vote
2
answers
63
views
UNIQUE-PATH in P assuming LPATH is in P
We define the following languages:
LPATH = {<G, a, b, k>|G is an undirected graph that contains a simple path of length at least k from a to b}.
UNIQUE-PATH = {<G, a, b>| G is an ...
0
votes
0
answers
42
views
Is there a type of reduction that independently transforms different parts of an instance?
Is there some notion of a poly-time reduction that maps certain different parts of the instance independently, i.e., $f((x,y))\mapsto(f_1(x),f_2(y))$ where $(x,y)\in L\iff (f_1(x),f_2(y))\in L'$?
1
vote
1
answer
221
views
Which class is the language MAX-CLIQUE in?
We define $$ֿ\text{Max-Clique} = \{\langle G, k\rangle: \text{$G$ is an undirected graph, and the largest clique of $G$ has exactly $k$ vertices}\}$$
Is this language in $\text{NP}$ or in $\text{coNP}$...
1
vote
1
answer
151
views
How do you show Dominating Set is NP Complete
A dominating set of an undirected graph $G = (V,E)$ is a subset of
vertices $C\subseteq V$ such that every vertex $v\in V$ either belongs to $C$ or has a neighbor in $C$. The corresponding decision ...
0
votes
1
answer
28
views
P=NP iff for any two non-trivial languages A, B in coNP, A≤pB and B≤pA
Prove: $\text{P} = \text{NP}$ iff for any two non-trivial languages $A$ and $B$ in $\text{coNP}$, it holds that $A \leq_p B$ and $B \leq_p A$.
The part of assuming the reductions and proving $\text{P}=...
2
votes
2
answers
63
views
In class P, does decidability implies searchability?
I'm studying a course on Intro to Computability, and I couldn't find an answer.
Often, we refer to problems in $\text{P}$ as problems that we can "efficiently search a solution for" (where ...
0
votes
1
answer
54
views
Can we use XOR's forced branching to show that NP!=P
Backstory: As happens, every now and then, one encounters an idea, prompting the question: Could I use this to prove that NP==P, or vice versa NP!=P
So then, today I got to trying to show that NP!=P ...
3
votes
2
answers
112
views
Can a universal worst case problem instance exist?
Given a specific type of problem like sorting a list and a particular algorithm like insertion sort, I am aware that a particular instance of the problem is worst case complexity for the algorithm (i....
1
vote
2
answers
59
views
prove AP-SUM is NP-complete
EDIT: I had a translation error. Instead of "unuary", it's binary.
AP-SUM is the language defined in the following way:
A word in the language AP-SUM is a pair <S, t>,
so that S is a ...
1
vote
1
answer
22
views
Complete language in P∪{C,D}
given: C is a NP-coNP language, D is a coNP-NP language and P is the known time-complexity class.
assumption: NP ≠ coNP.
I need to determine if exists a language B, such that:
a. B ∈ P∪{C, D}.
b. for ...
1
vote
1
answer
29
views
Variant of the k-MST problem on directed graphs?
Consider a weighted directed graph G and a special node $u$ in $G$. Are there any complexity results and algorithms on finding a minimum-weight directed acyclic subgraph $S^*$ of $G$ that contains $u$ ...
0
votes
1
answer
33
views
Unusual language in NP
Under the assumptions $\text{NP} \neq \text{coNP}$ and $\text{P}\neq\text{NP}\cap \text{coNP}$, we need to prove that
there is a language $L$ that satisfies the following:
$L\notin \text{P}$.
$L\in \...
1
vote
0
answers
18
views
Optimally sampling edge weights on a graph
I am working on some network problems where we do not know the underlying edge weights on the network precisely. All we know is that for a (directed) edge $(u,v)$ in the network, the weight $w(u,v) \...
3
votes
1
answer
476
views
What role does the lower bound play in the statement of Savitch's Theorem?
Savitch's Theorem states that $\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right)$ for any function $f\in \Omega (\log(n))$.
I don't ...
1
vote
0
answers
26
views
Which restrictions of SMT problems are decidable and what is their complexity?
We can easily create a SAT solver that is guaranteed to halt with "SAT" or "Unsat", by simply enumerating all possible solutions. Afaik, SOTA SAT solvers like ...
2
votes
2
answers
40
views
Complexity of checking validity of downscaled game of life
This is a question I thought up. I'm quite confident the answer is NO, but I'm not sure how to show it, and I'm wondering if this is known.
Imagine you are given a video of a 2k by 2k grid of bounded ...
1
vote
0
answers
18
views
What is the computational complexity of finding the splitting field of a polynomial?
Suppose $K$ is a number field and $f \in K[x]$ is irreducible. What is the computational complexity of computing f.splitting_field()? I'm also interested in the ...
2
votes
1
answer
41
views
Generalizations of integer-programming for the polynomial hierarchy?
Integer programming is known to be NP-complete. We also know that each class in the polynomial hierarchy contains elements not contained in the ones below, so Integer programming is not complete for ...
3
votes
0
answers
44
views
How to Prove following Weighted Forest Problem is NP-hard?
I am studying the following Weighted Forest Problem, which is an optimization problem in graph theory focused on finding optimal forest structures in robust scenarios. The problem is defined as ...