Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

0
votes
0answers
10 views

Upper bound on Boolean circuits

Oded Goldreich states in his book Computational Complexity that the number of Boolean circuits having v vertices and s edges is at most $ (2\cdot {v\choose 2 }+v)^s$ (page 40). I understand the term $...
0
votes
1answer
17 views

Avl tree worst case height proof

The worst case height of AVL tree in 1.44 * log(n).How do we prove that? I read somewhere about Fibonacci quicks but did not understand it.
1
vote
2answers
25 views

What is wrong with this solution for $\mathcal{O}({\log({n \choose \frac{n}{2}})})$?

In this recitation on MIT OCW, the instructor uses Stirling's approximation to calculate that $\mathcal{O}({\log({n \choose \frac{n}{2}})}) = \mathcal{O}(n)$. However, I went through the following ...
2
votes
1answer
11 views

checking whether a language is turing recognizable

After reading about it in the textbook and in the web, i was wondering about the "turing recognizable" concept. so for instance, if i take a simple language like:"L = {< M > | M ACCEPTS < M >}",...
2
votes
1answer
63 views

Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?

One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a ...
1
vote
2answers
43 views

NP-Completeness and commutative property

If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$? My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.
0
votes
0answers
24 views

Probabilistic r-way cut set algorithm

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph. In this generalized version, instead of ...
0
votes
1answer
24 views

Problems in $\textbf{DSPACE}(\log^2 n)$

Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$ and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations ...
0
votes
0answers
36 views

RAM and Turing machines: time complexity of simulation

My RAM machine is very simple: it has $k$ tapes, an input tape and one special control tape it has an infinite memory (array called $A$) which can be accessed randomly the control tape is read ...
2
votes
2answers
64 views
+50

How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
0
votes
1answer
51 views

How do I prove that SPACE($n^{555}$) $\neq$ NP?

I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.
2
votes
0answers
32 views

Decision problems with complex input validation

In an answer to a question regarding input validation in decision problems, @Apass Jack wrote It is easy to check whether a problem instance is a valid instance or not for almost all decision ...
0
votes
0answers
38 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
2
votes
1answer
62 views

Reduction to a vertex cover problem-like with weighted vertices and edges

Description Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas: $G$ is an undirected graph $K \le |V|$ $L > 0$ is the maximum limit Each vertex $v \in V$ has a weight $...
1
vote
1answer
20 views

Changing probabilities to 0/1 in definition of class IP

A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$, $$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$ $$w\notin L\Rightarrow Pr[V\...
-3
votes
0answers
38 views

Does P=NP? (The big question) [closed]

If you know much about theoretical computer science, you have heard the question before. This site has plenty of questions posted about the implications of one answer or another to this question (...
0
votes
1answer
36 views

Complexity of an encoded turing machine

This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it. First, we have the variable m which is a ...
2
votes
1answer
75 views

Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
0
votes
0answers
14 views

BP as an operator

The class $BP.C$ (BP operator applied to the complexity class C) is defined as in this paper. $BP.C$ is the set of all languages $L$ such that there is some polynomial $p$ and some set $A \in C$ ...
1
vote
2answers
28 views

Running time complexity of finding maximal power of divisor that divides natural number

Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
0
votes
0answers
12 views

Proving k-partition problem is NP [duplicate]

For any integer k ≥ 2, the k-Partition problem is said to be a sequence of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums? I'm confused on ...
1
vote
2answers
40 views

Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset? I'm ...
3
votes
0answers
73 views

A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM Inputs: Positive integers $a$ and $b$ with $a \ne b$, and positive integers $k$ and $t$, with $k$ specified in unary. Encoding: These inputs (...
3
votes
1answer
49 views

Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
2
votes
0answers
24 views

Implementing depth-3 circuit for XOR

In this set of notes, they claim that there is a size $O(2^{\sqrt n})$ depth-3 circuit (OR -AND -OR) that implements XOR. I tried for a little bit to figure out how to do this, but couldn't find ...
-2
votes
0answers
26 views

Please help me with exercise 6.3.3 of László Lovász Computational Complexity lecture notes

Let us call a Boolean formula with n variables simple if it is either unsatisiable or has at least 2^n / n^2 satisfying assignments. Give a probabilistic polynomial algorithm to decide the ...
1
vote
1answer
37 views

Does a polynomial solution to weakly-NP Complete problem mean P = NP?

Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.
0
votes
0answers
13 views

Question regarding EXPTIME Completeness and NP Hardness

Based on the links below I wonder whether there would be some explicit EXP Complete problems which are NP Hard even when encoded in unary. Care to help me? How to use succinct circuits to construct ...
0
votes
0answers
21 views

What is the complexity of an algorithm that ensures 2 “aggregate graph properties”?

Background Let $G(V,E)$ be a graph. Let $S$ be the set of all combinations of $|V|$ edges. Let $A$ & $B$ be two subsets of $S$, where: each subset is a collection of all elements of $S$ that ...
9
votes
1answer
718 views

Why isn't P and P/poly trivially the same?

The definition of P is a language that can be decided by a polynomial time algorithm. The definition of P/poly can be taken to mean a language that can be decided by a polynomial-size circuit (see ...
2
votes
1answer
34 views

On propositional formula satisfiablitiy

I know that there is no algorithm for converting any logical formula to DNF so even though we have an efficient algorithm to solve DNFSAT we can't solve formulaSAT in deterministic polynomial time. ...
-2
votes
1answer
39 views

Prove PSPACE is closed under union?

How would you prove PSPACE is closed under union? So far, my thought process is that we can create an algorithm to show that P is closed under union. I'm struggling with how I can connect that to ...
-2
votes
1answer
58 views

Prove PSPACE is closed under complement? [duplicate]

How would you prove PSPACE is closed under complement? So far, my thought process is that we can create an algorithm to show that P is closed under complement. I'm struggling with how I can connect ...
1
vote
1answer
20 views

Minimum number of tree operations to normalize a labeled tree

Given a binary tree with labels on the leaves, like $(bc)(ad)$ or $((af)e)(c(db))$, which we can interpret as a product of terms with respect to a commutative associative operation, how many ...
0
votes
0answers
18 views

Hardness of fixed instance of computational problem

Why is it the case that formally a fixed instance of a computational problem cannot be hard, only a computational problem with a large instance set qualify?
-3
votes
1answer
38 views

Exponential amount of information in polynomial size? Impossible!

I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183: Formula $F$ has a highly regular structure. It has $|x|$ ...
1
vote
1answer
32 views

Turing Machine where branches are resolved via arbitrary operator

Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
0
votes
0answers
14 views

Analyze the following algorithm by computing its running time, T(n) [duplicate]

I'm trying to figure out the running time of this loop. I think it's T(n) = 0(n^4) because the loop inside is dependent on the i of the outer loop. So does that mean the inner loop will have a running ...
4
votes
1answer
120 views

Doing matrix multiplication with $\lceil n^3 / \log n \rceil$ processors in $2\log n$ steps by Brent's principle

On a parallel machine with $n$ processors we can compute the sum (or product, or the result of any associative operation) on $n$ numbers in $\log n$ steps. In the first step combine neighbors to get $...
2
votes
1answer
23 views

What is the motivation behind “ Descriptive Complexity ”?

Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". ...
1
vote
0answers
26 views

What are some of the most important results from “Implicit computational complexity” theory?

I just found out about implicit computational complexity theory. It seems very interesting. I would like to know more about it. For me to get an overview of the results of the field, what are ...
1
vote
1answer
65 views

What is the complexity of the algorithm to calculate power set of a set?

Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality n, there is a for loop ...
1
vote
0answers
22 views

Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?

The book I am reading is suggesting the following: Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(...
2
votes
1answer
51 views

What is an optimal algorithm?

I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are ...
3
votes
1answer
37 views

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens?

If $NP\subseteq DTIME[n^{O(\log n)}]$ then what happens? Does it imply $NP\neq EXP$? Is there any other consequences such as $BPP\neq EXP$? Does it also give $PSPACE\subseteq DTIME[n^{O(\log n)}]$?
3
votes
2answers
46 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following langugae is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
0
votes
0answers
23 views

Reduction of complement from complexity class co-np and p

Let P $ \neq $ NP. D is in the complexity class co-NP. B is in the complexity class P. Let $ \bar{D} $ be the complement of D, then $\bar{D} $ $\leq _ {p} $ B. Is this statement true or false? My ...
2
votes
1answer
49 views

Reducing the vertex cover problem to a variation of the vertex cover problem [duplicate]

The following variation on the vertex cover problem was given: Given is an instance of graph $G = (V, E)$. Does $G$ have a vertex cover of size at most $\frac{|V|}{4}$? I was asked to prove that ...
1
vote
1answer
52 views

Is there a polynomial-time reduction from a NP-hard problem to the complement of tautology?

Is the following true or false? Why? Let $Y$ denote the complement of the tautology problem. If a problem X is NP-hard, then there is a polynomial-time (many-one) reduction of $Y \leq_{p} X$.
0
votes
1answer
18 views

Behavior of specific PDA for a certain input

Suppose we're given the non-deterministic PDA shown below which reads from the alphabet $\sum = \lbrace a,b \rbrace$. How will this PDA behave if we pass it the string $ba$? We read $b$ first and push ...