# Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

4,119 questions
Filter by
Sorted by
Tagged with
9 views

### Understanding definition of #P

Valiant defined $\#P$ in terms of a counting TM, which is a NTM that outputs the number of solutions . I am a bit stuck with the following two questions: Let's say I have a decision problem $X$, ...
7 views

### Out-Degree of a Configuration Graph

In Chapter 4 in Computational Complexity by Arora and Barak it states, regarding the configuration graph of a Turing Machine, that If M is deterministic, then the graph has out-degree one, and if M ...
20 views

### Is $DSPACE(n^8) \subset NSPACE(n^5)$?

I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold. I know from Savitch's Theorem that: $$NSPACE(n^5) \subseteq DSPACE((n^5)^2) = DSPACE(n^{10})$$ If the ...
30 views

### What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to

What are the $EXP^{NP}$, $EXP^{PSPACE}$, and $EXP^{EXP}$ equal to? I suspect that their, NEXP, ESPACE and 2EXPtime respecitvely. And what bout $NP^{EXP}$
53 views

### Do all languages in $P$ have polynomial proofs that they are in $P$?

A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. ...
29 views

### k-limited solution for PCP

So there's following problem, that has been bugging me for the last few days: A solution of a PCP $i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
19 views

### Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

As said in the title, i am quite curious wether NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n)) I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n)) due to linear space reduction (i.e. ...
4k views

### Is Group Theory useful in Computer Science in areas other than cryptography?

I have heard many times that Group Theory is highly important in Computer Science, but does it have any use other than cryptography? I tend to believe that it does have many other usages, but cannot ...
11 views

### Circuits and formulas for Clique

Is it correct to say that the Clique Problem is in $P$ iff there exists a family of Boolean circuits $C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that ...
3k views

### Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are $O(1)$. def is_equal(a: int, b: int) -> bool: return a == b <...
26 views

### Complexity analysis of m!/n!(m-n)!

Given the runtime of an algorithm to be m!/(n!*(m-n)!) That is mCn, where both m and n are variables, is the complexity factorial or polynomial? Or is it something else? Please elaborate. Thanks
34 views

### Smallest Circuit for Square of Sparse Symmetric Matrix

I have an n by n symmetric matrix, and I would like to compute its square in as small a circuit complexity as possible. It's sparse: there are sqrt(n) nonzero entries in each row/column, so the input ...
35 views

### Is my reasoning wrong that $PSPACE$ should not equal $EXPTIME$?

It's impossible for a problem to require exponential space without being exponential-time. Consider that if an $EXPSPACE~~complete$ problem can be solved in $2^n$ time. It will now fall into the ...
11 views

### Configurations and CNF formula for neighboring configuration

A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its ...
19 views

### Buckets of Water Problem - Part 2

Continuing from this question: The buckets of water problem (All the definitions can be found there, so I will not repeat them). As seen there by Yuval's answer, the problem is NP-Hard. I was ...
146 views

### Counting on a matrix

I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$. If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are ...
137 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 ...
103 views

### Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with ...
29 views

### What are the three points of view in Kolmogorov Complexity?

I was reviewing for my finals and find this question that I have totally no clue. Compare the following to statements from three points of view: There exists a constant $c > 0$ such that for all ...
31 views

### Arthur-Merlin protocol

I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$. We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not ...
26 views

### How do you represent an r.e. complexity class with a list of TMs?

In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices ...
115 views

### The most subtle NP-“intermediate” problem

What is the $NP$ problem whose status in $P$ or $NP$-complete is still unsettled, as of 2018? This question is inspired by the following two recent breakthroughs: The work of Mulzer et. al on $NP$-...
50 views

### Enumeration of a class of languages

Can you enumerate a class of languages in such a way that the description of every language/ machine enumerated encodes where it was in the enumeration? Ex:if you are given the description of the bth ...
42 views

### TSP 200-approximation, given $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ for all nodes $x,y,z$

Input: complete, undirected graph $G=(V,E)$ and cost function $c$ Assume for all nodes $x,y,z \in V$: $c(x,z)\le c(x,y) + 100\cdot c(y,z)$ Find a 200-approximation polynomial time algorithm for the ...
12 views

### Computaional Complexity of Frobenius Norm

How can I calculate the computaional complexity of Frobenius norm of each column vector(M X 1) in a M X N matrix and finally sorting the norm values in descending order? To clarify I have N-column ...
159 views

### Space complexity of breadth-first search

I read that breadth-first search has to store (at most) $1+b+b^2+···+b^d$ nodes in memory ---more than depth-first search---, where $d$ is the depth of a solution, and $b$ is the branching factor. ...
39 views

### turing machine accepting language {ww} has ω($n^2$)

prove or disprove that any turing machine which accepts language $l=\{ww | w ∈ \{0, 1\}∗ \}$ has time complexity $ω(n^2)$
97 views

### Is the two-color leapfrog problem in P?

My question is whether a specific decision problem is in P or not. It's straightforwardly in NP. The decision problem is a specific case of the general $k$-color leapfrog problem. I can already show ...
27 views

### Does P not NP imply NP COMPLETE disjoint from RP?

According to Wikipedia https://en.wikipedia.org/wiki/RP_(complexity), $P \ne NP$ implies that $RP$ is a strict subset of $NP$. Does anybody have a reference? Furthermore, am I correct that if this ...
21 views

27 views

### What algorithm should I use to find the closest solution to a given total using a list of integers?

My problem is this: Let's say I have an arbitrary list of integers A[2013, 54, 3, 32 1, 23...] What is the best strategy to find which of those numbers I should add together to have a sum equal or ...
13 views

### How to generate a uniform random sample of unique vertex pairings from a undirected graph under constraint?

I'm working on a research project where I have to pair up entities together and analyze outcomes. Normally, without constraints on how the entities can be paired, I could easily select one random ...
29 views

### why is $\Pi_2$ smaller than $NP\cap coNP$

Consider the language $A=\{(\phi_1, \phi_2) | \phi_1 \in SAT, \phi_2\in \overline{SAT} \}$. What is the smallest class that $A$ is known to belong to? Apparently, the answer is $\Pi_2$, although I ...
17 views

### If $NTime(2^n) \subseteq DTime(n^n)$, then what can you conclude about $DSpace(n^n)$?

Assume $NTime(2^n)\subseteq DTime(n^n)$, what can you conclude about $DSpace(n^n)$? I don't know if this is the correct approach, but here was my attempt at an answer: Let $A \in DSpace(n^n)$ and ...
17 views

### complexity of dividing set of number with constraints

I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem. There is a set of $n$ positive ...
23 views

### Splitting a group of numbers into $k$ sorted groups

I have this first task: You have a set of numbers $S =\{ \dots \}$ of length $n$. And a number $k$. Both $n$ and $k$ are powers of $2$ and: $1 < k < n$ Your task is to write an algorithm (...
193 views

### What is the goal of studying all those NP-complete problems?

So i'm currently reading a lot of things about graph NP-complete problems, and it seems that the goal of a lot of researchers is to find new results about their complexity, results like "...
21 views

### number of constraints and variables

i have the following formulation and I want to know the number of variables and constraints
13 views

### Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$

Can you give an example of a problem in $EXP^{RE}$ but not In $P^{RE}$?
23 views

### Why minimum vertex cover problem is in NP

I am referring to the definition of the minimum vertex cover problem from the book Approximation Algorithms by Vijay V. Vazirani (page 23): Is the size of the minimum vertex cover in $G$ at most $k$? ...
24 views

### Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

I'm having a small issue with wikipedia's proof that $RP \subseteq NP$: An alternative characterization of RP that is sometimes easier to use is the set of problems recognizable by nondeterministic ...
68 views

### “Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?

This problem is not decidable (reducible to halting problem) but is semi-decidable and therefor verifiable (as those two definitions are equivalent: How to prove semi-decidable = verifiable?). However,...
67 views

### Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?

In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.): Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real ...
20 views

### 2 SAT NL algorithm

How would you define the 2-SAT complement pseudo code? The information I gathered is, Let x be random variable chosen then we have to check if there exist a path between x to ~x and from ~x to x. If ...
62 views

### Complexity of enumeration vs complexity of counting

I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm. Now, I have problem with the following. ...
117 views

### Is the leapfrog automata problem in P?

My question is whether a specific decision problem—finding a computation path through a "leapfrog automaton"—is in P or not. It's straightforwardly in NP, and it resembles the hamiltonian ...
29 views

### How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

How to prove if P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP? OR P = NP if NPC intersects with Co-NPC