Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
-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

What is the intersection between CFL and REG languages?

The question is mentioned down here:
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)$?

1 2 3 4 5 78