Questions tagged [complexity-theory]

Questions related to the (computational) complexity of solving problems

Filter by
Sorted by
Tagged with
0
votes
0answers
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 [1]. I am a bit stuck with the following two questions: Let's say I have a decision problem $X$, ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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}$
0
votes
1answer
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. ...
0
votes
0answers
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$-...
0
votes
1answer
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. ...
17
votes
8answers
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 ...
2
votes
1answer
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 ...
9
votes
7answers
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 <...
0
votes
1answer
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
1
vote
1answer
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 ...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
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 ...
9
votes
1answer
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 ...
-2
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
-1
votes
3answers
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$-...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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. ...
-1
votes
1answer
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)$
8
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
21 views

If $PSPACE^{SAT}=PSPACE$ and $PSPACE \subseteq EXP$, then why does $EXP^{SAT}$ not necessarily equal to $EXP$?

I read the following claim: $PSPACE^{SAT}=PSPACE$ $EXP^{SAT}$ is not necessarily the same as $EXP$ The first claim makes sense; $PSPACE \subseteq PSPACE^{SAT}$ trivially, and for any language $B \in ...
1
vote
1answer
41 views

Best case “skew height” of an arbitrary tree

Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\...
0
votes
3answers
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 ...
3
votes
0answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 (...
4
votes
1answer
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 "...
-5
votes
0answers
21 views

number of constraints and variables

i have the following formulation and I want to know the number of variables and constraints
0
votes
0answers
13 views
2
votes
1answer
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$? ...
0
votes
1answer
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 ...
0
votes
1answer
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,...
2
votes
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
1answer
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. ...
8
votes
1answer
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 ...
-1
votes
1answer
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
0
votes
0answers
16 views

What's the running time for the following clique algorithm?

I sometimes like to puzzle over some NP-complete algorithms (I know how microscopic the chances are to find something new but I find it relaxing) and came up with something that I don't really know ...
7
votes
3answers
890 views

Computation Complexity books for a mathematician

I recently attented to some computational complexity talks (or complexity theory, I am not sure which is the correct name) and I fell in love with it. I would like to find some books, online courses......

1
2 3 4 5
83