Questions tagged [complexity-theory]
Questions related to the (computational) complexity of solving problems
3,855
questions
-1
votes
1answer
17 views
How to create CFG for $L := \{x| \#_0(x) \text{ is even and } \#_1(x) \text{ is odd}\}$
Create an CFG for all strings over {0, 1} that have the an even number of 0’s and an odd number of 1’s.
Also, I have a hint
HINT: It may be easier to come up with 4 CFGs – even 0’s, even 1’s, odd 0’s ...
1
vote
1answer
21 views
How are “Problem Complexity” and “Solution Complexity” different?
I am in an algorithms course, and my professor keeps specifying "we are talking about Problem complexity here, not Solution complexity". I would like to gain an intuitive understanding of the ...
0
votes
1answer
16 views
Triple nested loop complexity
I'm trying to determine the complexity of the following structure:
for (i = 1; i < n; i++)
for (j = 1; j < o; j++)
for (k = 1; k < p; k++)
...
4
votes
1answer
50 views
Two versions of Subset Sum Problem
I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is:
Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
0
votes
1answer
17 views
simple question about epsilon and estimation turing machines
i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
-1
votes
0answers
17 views
algorithm for a #SAT oracle (#SAT algorithm)
i tried to look for an algorithm that decides whether an input x is in #SAT or not.
$\#SAT$ is defined, at least in this case to be: $<\phi ,k>=\left\{\phi \:is\:a\:boolean\:formula\:with\:at\:...
0
votes
0answers
16 views
algorithm that finds minimal vertex cover of a given vertex
i am looking for a simple algorithm that gets as an input an undirected graph and a vertex in the graph and outputs the minimal vertex cover that v belongs to.
not sure on how to do it correctly, ...
-1
votes
0answers
18 views
Finding an algorithm that after removing k edges we get an acyclic graph [duplicate]
Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k,...
1
vote
2answers
52 views
NP-complete problem whose corresponding optimization problem is not NP-hard
For this question I will refer to$\ NP-hard$ problems as those that are at least as hard as$ \ NP-complete$ problems. That is, a problem$ \ H$ is$\ NP-hard$ if there is an$ \ NP-complete$ problem$\ G$,...
0
votes
1answer
15 views
Reducing vertex cover to minimal vertex cover
What is a quick and a elegant way to reduce vertex cover to minimal vertex cover?
Is it possible to use vertex cover as verifier in the algorithm that reduces vertex cover to minimal vertex cover? ...
1
vote
1answer
40 views
Connection between vertex cover and P=NP
I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.
In an undirected graph $G(V,E)$, ...
0
votes
0answers
6 views
Are all NP-complete languages downward self-reducible?
Arora-Barak says that using the Cook-Levin reduction, one can show that all NP-complete problems are downward self-reducible. I know that SAT is downward self-reducible but I am not able to see how we ...
0
votes
0answers
13 views
Proving existence of feedback edge set variant based on deciding if digraph acyclic [duplicate]
NOTE: this is a variation of Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC. here the definition of ACYCLIC is different to make it easier for me to understand a ...
0
votes
0answers
25 views
Sliding Puzzle w/ multiple solutions
I am trying to write an algorithm which produces a solution to a modified n by n sliding puzzle (assuming that an end state is reachable from the given start state). The change is as follows: tiles ...
0
votes
1answer
31 views
Construct a PDA for at least one $w_i$ $\neq$ $w_{i + 1}^r$?
My assignment asks
Let $S =
\{
w_1\#w_2\# \dots \#w_k | k ≥ 2; (∀i ≤ k)w_i ∈ \{0, 1\}^\star
; (∃i < k) w_i\neq w_{i + 1}^r$
, i.e., not every string $w_i$ is equal to the reversal of $w_{i+1}$. ...
0
votes
1answer
38 views
Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC
i don't understand the following:
If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting ...
1
vote
1answer
10 views
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):
"More ...
-1
votes
0answers
26 views
0
votes
1answer
22 views
Does input space size contribute at all to the runtime of an algorithm?
I just started learning about NP-Complete problems and one of the first examples they give is Set Cover:
Given a set $U$ of $n$ elements, a collection $S_1, \ldots, S_m$ of subsets of $U$, and a ...
2
votes
1answer
39 views
Special Monotone SAT problem: NP complete?
Say we have the set $X=\{ x_1, x_2, \dots \}$ of variables. Then we consider the following problem: Is the formula
$$\bigwedge_{(a,b,c) \in A}(a \vee b \vee c) \wedge \bigwedge_{(a,b,c) \in B}(\neg a ...
0
votes
1answer
58 views
Sorting almost sorted array
Encountered this question but I couldn't solve with the complexity they solved it:
Suppose I have an array that the first and last $\sqrt[\leftroot{-2}\uproot{2}]{n} $ elements has $\frac{n}{5}$ ...
0
votes
1answer
28 views
Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi
We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.
...
4
votes
0answers
50 views
+50
Are weakly polynomial time algorithms truly polynomial?
I've been looking through a ton of sources to try and understand the definitions of strongly and weakly polynomial time algorithms. Wikipedia
states an algorithm runs in strongly polynomial time if
...
1
vote
0answers
20 views
Storing a configuration of nondeterministec machines in log space
In Sipser's book page 351:
Recall that Savitch's theorem shows that we can convert nondeterministic TMs to deterministic TMs and increase the space complexity $f(n)$ by only a squaring, provided ...
6
votes
1answer
86 views
Select at least one from each category to minimize union, NP-hard problem?
I have this problem that is very similar to the minimum k-union problem:
Given a collection $C$ of subsets of a finite set $S$ and each set $c\in C$ has a label that is its category. The problem is ...
2
votes
0answers
35 views
Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist
Hello and thank you for helping me understand the following:
I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space.
context: Defining ...
0
votes
0answers
12 views
Is DHAMPATH downward self-reducible?
DHAMPATH is the set of all the directed graphs which have a hamiltonian path. It's a well known NP-complete problem.
I know the proof of SAT's downward self-reducibility. Arora-Barak says Cook-Levin'...
1
vote
1answer
31 views
Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $
How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}.
My try:
Construct a ...
4
votes
0answers
33 views
Why the Cook-Levin reduction is not a parsimonious reduction?
In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is ...
1
vote
2answers
60 views
Computational complexity vs other complexities
Complexities, such as time complexity, space complexity, communication complexity and sample complexity, are often used to analyze the performance of algorithms. As far as I know, time complexity and ...
0
votes
1answer
23 views
How will I calculate the time and space complexity for this pyramid algo?
This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345":
...
-4
votes
0answers
34 views
theory of computation [closed]
k-clique is a subgraph which has k vertices and there is an edge between every two vertices. Prove that 3-clique ∈ P. In other words, give an algorithm/TM that decides 3-clique in polynomial time.
4
votes
1answer
46 views
why does $ A≤_p \#SAT$ if $A \in BPP$
hello and thank you for helping me understand the following:
I really don't understand this, why if language $A \in BPP$ then $A≤_P\#SAT$?
language A is in BPP class, if for a probabilistic turing ...
3
votes
1answer
95 views
Polynomial-time linear-reduction from Directed Hamiltonian Path Problem to 3SAT
Is there a polynomial-time reduction from Directed Hamiltonian Path Problem to 3SAT which is linear in the number of vertices? That is, it reduces every directed graph $G$ with $n$ vertices to a ...
2
votes
0answers
21 views
Existence of a P-Complete language with space($\log\log n$) reduction
I have been reading and searching and I still cannot understand if there exists a language as following:
Can a language be P-complete with respect to $\mathsf{Space}(\log \log n)$ reductions?
...
0
votes
2answers
32 views
Is there a language which has a polynomial length certificate but not known to have a polynomial time verifier?
The question came to my mind while studying the NP definition. Do we know any such languages?
0
votes
0answers
37 views
What can be said about complexity class of a problem if there exist a pseudo-polynomial verification algorithm?
Let X be a problem for which pseudo-polynomial algorithm time for verification of solution exists. What can be said about complexity of problem X? Can X belong to NP-hard class?
2
votes
1answer
84 views
Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge
Consider a directed graph on n vertices, where each vertex has exactly
one outgoing edge. This graph consists of a collection of cycles as
well as additional vertices that have paths to the cycles,...
1
vote
0answers
13 views
Why are bottom-up selector matching algorithms more efficient?
Most implementations of CSS-like selectors (that is, patterns that may match paths in a tree) seem to use a bottom-up approach. That is, for each node in the tree, they check for a match against the ...
1
vote
2answers
47 views
Is the number of NP-complete problems finite?
It should be straight forward to show that there are infinitely many NP-hard problems:
Proof:
Take the problem Remove 1 Vertex 3-COL ($R1V3COL$) which takes a graph $G=(V,E)$ as an instance and ...
0
votes
1answer
16 views
Compendium of approximation ratios, with narrower scope and more up to date than the NP-compendium?
I usually check the NP-compendium from Pierluigi Crescenzi, and Viggo Kann when I want to know the APX status and approximability results of a problem.
However, I understand that maintaining it is a ...
-1
votes
1answer
57 views
Are there any NP-hard problems for which the following statement is true:
$\overline{A} \le A\ and $ $A \le \overline{A}$
Is the following proof correct?
If $\overline{A} \le A \Rightarrow \overline{A} \in NP$ since A is NP-hard $ \Rightarrow A \in coNP$
Since $\...
-3
votes
0answers
49 views
What are some generalizations of the tree diameter?
I am specifically interested in extensions and generalizations of the diameter concept on graphs. I can't find anything relevant in google scholar.
I have a certain result about tree diameters that ...
2
votes
1answer
54 views
NP-completeness of a problem with pretty fast algorithm
Supposing if a problem with $n$ non-deterministic bits is in $O(2^{\alpha n})$ time at every $\alpha\in(0,1)$ then is there evidence that problem can or cannot be $\mathsf{NP}$-complete?
1
vote
0answers
78 views
Class of languages recognizable by n-bit formulas of size at most $T(n)$
A Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-...
3
votes
0answers
22 views
Bit complexity of computing the sign of an expression evaluated at an algebraic number
I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
2
votes
0answers
36 views
Circuit complexity of random Boolean functions
I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why ...
2
votes
1answer
47 views
Set which is easy to sample, but difficult to sample from its complement
Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
2
votes
0answers
21 views
Deciding Intuitionistic Logic via QBF
I want an algorithm to decide whether a theorem holds in propositional Intuitionistic logic ($IL$). We know $IL$ is $PSPACE$-complete, so we should be able to reduce $IL$ to $QBF$.
In Literature i ...
3
votes
1answer
132 views
Is O(n log n) exponential speedup over O(n^2)?
I would like to know if $O(n \log n)$ is an exponential speedup over $O(n^2)$?
