Skip to main content

All Questions

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
Bongus01's user avatar
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 ...
Frank Vega's user avatar
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)$ ...
Turbo's user avatar
  • 2,919
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 ...
puzzler's user avatar
  • 11
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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$. ...
Xoxoxo's user avatar
  • 25
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 ...
user43464's user avatar
  • 131
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 ...
user1337's user avatar
  • 121
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 ...
CuriousScientist's user avatar
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 ...
User198's user avatar
  • 103
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 ...
squancy's user avatar
  • 119
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}\...
user avatar
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 ...
Student's user avatar
  • 231
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 ∈ \...
user avatar
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 $𝑀(...
user avatar
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 ...
Penny Dreudter's user avatar
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$...
user avatar
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 ...
Steeve's user avatar
  • 11
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] ...
user avatar
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] ...
user avatar
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$...
user avatar
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 ...
Fraser's user avatar
  • 11
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 ...
Jaimi's user avatar
  • 85
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^...
Aldew's user avatar
  • 111
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 ...
Omer Sade's user avatar
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: ...
NotAGroupTheorist's user avatar
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 ...
Aurelia's user avatar
-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 ...
Aditya Mishra's user avatar
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 ...
Dee's user avatar
  • 141
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'$?
Rincewind's user avatar
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}$...
Dee's user avatar
  • 141
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 ...
Nicolò Bonacorsi's user avatar
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}=...
Dee's user avatar
  • 141
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 ...
Yup8's user avatar
  • 21
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 ...
Simon's user avatar
  • 15
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....
NotAGroupTheorist's user avatar
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 ...
Dee's user avatar
  • 141
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 ...
Dee's user avatar
  • 141
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$ ...
alcatraz's user avatar
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 \...
Dee's user avatar
  • 141
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) \...
alcatraz's user avatar
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 ...
Katelyn Hooper's user avatar
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 ...
user56834's user avatar
  • 4,122
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 ...
hmmmmmmm's user avatar
  • 121
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 ...
Jackson Walters's user avatar
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 ...
user56834's user avatar
  • 4,122
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 ...
Toyllo's user avatar
  • 31