Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

14
votes
2answers
1k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
1
vote
2answers
57 views

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

I'm so bad at solving the problem of the type "If A is an NP complete problem, B is reducible to A, then B is..." that I have to come here and ask these silly questions each and every time I encounter ...
-1
votes
1answer
36 views

Proving that the set of non-universal CFGs is not in NP

How do I prove that $\overline{\mathrm{ALL_{CFG}}}$ does not fall in NP, where $\qquad\mathrm{ALL_{CFG}} = \{\langle G \rangle \mid G \text{ is a CFG}, L(G) = \Sigma^* \}$
7
votes
1answer
275 views

What is it called when two problems are similar?

Suppose that there are two problems $P$ and $Q$. How can I say that "solving $P$ is same thing with solving $Q$"? For instance, if $P$ is NP-Hard, then we can say "$P$ can be solved in polynomial ...
3
votes
2answers
48 views

Can someone provide a trivial example to the “reduction” procedure used to prove hardness? [duplicate]

I cannot comprehend how you can prove hardness between two NP complete problems. For example, let X be a NP hard problem, I want to prove Y is also NP hard. I can do this by reducing X to Y, if Y is ...
0
votes
1answer
25 views

If A is polynomial time reducible to B such that B <= A, does it mean B must be a polynomial time algorithm?

I don't understand what it means for A to be polynomial time reducible to B. I'm guessing is that we can revised the algorithm some how such that it becomes B, where B is a polynomial time algorithm. ...
10
votes
3answers
919 views

Has the graph isomorphism problem been solved?

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not ...
0
votes
1answer
44 views

Non-deterministic algorithm to check if a list has some given value

I know that I can build a non-deterministic algorithm with a CHOICE function that verifies if a value x is in an array in O(1) ...
3
votes
3answers
299 views

Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?

To prove that some decision problem $A$ is NP-complete, my understanding is that it suffices to show that the problem is in NP (i.e. that one can verify or reject all statements in polynomial time), ...
1
vote
0answers
17 views

MaxSNP flow problems

Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
2
votes
1answer
47 views

If P = NP, why does P = NP = NP-Complete? [duplicate]

If P = NP, why does P = NP also then equal NP-Complete? I.e. Why would it then be the case that ...
3
votes
1answer
139 views

Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds?

I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world. However, is it possible to ...
6
votes
2answers
88 views

Analog of PP for computability rather than complexity?

The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the ...
4
votes
6answers
1k views

How is it valid to use oracles in mathematical arguments?

Oracles do not exist. If one did exist, then you would replace them with a subroutine with computational requirements and you would no longer need an "Oracle". Thus, Oracles do not exist almost by ...
3
votes
2answers
29 views

Function that is not Space Constructible

I'm reading Sipser's Introduction to the Theory of Computation, and I'm reading about space-constructible functions. He gives the following definition: A function $f: \mathbb{N} \to \mathbb{N}$ is ...
6
votes
0answers
72 views

Is finding a weight-balanced tree NP-hard?

In the following, we are considering binary trees where only the leaves have weights. Let $T$ be a binary tree and $W(T)$ be the sum of its weighted leaves. Let $T.l$ and $T.r$ be the left child and ...
2
votes
0answers
25 views

How to convert a rank constraint into integer programming?

Consider the low-rank matrix completion problem: given an integer $k$ and a subset of entries of some matrix, can you fill in the rest of the entries so that the resulting matrix has rank at most $k$? ...
-3
votes
1answer
91 views

Showing that M is NP-Complete

An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that each item in $T$ belongs to some $S_i$, and ...
3
votes
1answer
97 views

Why are non-relativizing proofs preferred to relativizing ones?

I apologize, but even after these two other posts: here and here I'm still having trouble understanding oracle TMs and relativization. This question comes at the issue from a different angle: Why ...
2
votes
1answer
105 views

MAX3SAT proof help? Showing that NP = coNP iff MAX3SAT is in NP

For a 3CNF $\phi$, denote by $c(\phi)$ the largest number of clauses satisfied under an assignment. Define: $\mathrm{MAX3SAT} = \{\langle\phi, k\rangle\mid c(\phi) = k \text{ and }\phi\text{ is a ...
1
vote
0answers
53 views

Would this be true for complexity classes? [duplicate]

For each integer k > 1, define the complexity class: $QP_{k}:= \cup_{c>0} Time(2^{c * log^{k} n})$ Then for all integers k > 1, $QP_{k} \subset QP_{k+1}$. Would this be a true assertion? ...
0
votes
0answers
24 views

Algorithms for verifying and solving three-coloring [duplicate]

I found the following problem that I am trying to answer: Consider the three color problem where V, vertex set of a bipartite graph. can be partitioned into three subsets such that there is no ...
2
votes
1answer
165 views

Why does the Time Hierarchy Theorem not relativize?

Is it true that $DTIME^A(n^k) = EXP$ for any fixed $k$ and EXPTIME-complete oracle $A$? If not, what do these complexity classes equal and why (because I know that $P^A = EXP$ for any ...
0
votes
0answers
35 views

Reduction of specific scheduling problem to show np-completeness

Given a Set K of n tasks, a set T of t possible time-intervalls to schedule any task, and a number k: Is there a schedule for the tasks, such that there are at most k conflicts (time - overlaps) of ...
1
vote
3answers
58 views

If A is in P and B is non-trivial, then A ≤p B [duplicate]

On wikipedia's article on Polynomial-time reduction it states: Every nontrivial decision problem in P (the class of polynomial-time decision problems, where nontrivial means that not every input ...
5
votes
2answers
95 views

How does the use of oracle Turing machines not lead to contradictions?

How can we ensure that we are continuing to make sound and valid statements about complexity classes when using oracle Turing Machines? According to my understanding (based on the definitions given ...
5
votes
2answers
159 views

algorithm time analysis “input size” vs “input elements”

I'm still a bit confused with the terms "input length" and "input size" when used to analyze and describe the asymptomatic upper bound for an algorithm Seems that input length for the algorithm ...
1
vote
1answer
45 views

Can a CS grad student work on quantum field theory and string theory problems? [closed]

The mathematical aspect of particle physics theory are interesting and there seems to be a lot more connections being made to computation and information (like with complexity theory having some ...
1
vote
1answer
57 views

Can oracle arguments separate P and NP?

I know that the general consensus among CS researchers is that non-relativizing techniques will be needed to separate P and NP. However, if there is an oracle language $A \in \textbf{P}$ such that ...
4
votes
1answer
30 views

3 dimensionnal matching to partition transformation

We want to transform $3DM$ to $PARTITION$, I am reading Garey and Johnson book and I really don't understand how they do the transformation, I know how they create elements $a_i$ from triples of set ...
1
vote
0answers
30 views

Connection between formula size and time complexity

Supposing we have a problem $P$ with input size $n$ encoded as a boolean formula $f$ in $n$ variabes which is a multilinear polynomial. Let $f$ have the smallest degree. Is there a connection between ...
1
vote
1answer
18 views

Function with minimum sensitivity

Let sensitivity be defined as in Sensitivity and Block sensitivity Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$? Is ...
3
votes
1answer
54 views

Assign undirected edges in a mixed graph to make graph cyclic/acyclic

What is the complexity of the following problem? Given a mixed (some edges directed, some undirected) graph, assign a direction to all the undirected edges to make the graph contain a cycle. It ...
0
votes
1answer
35 views

All but Five Three Colorable

An NP Problem Named All But Five Three Colorable(AB53C) is defined as follows :- Input : Connected Graph G(V,E) The Connected Graph is AB53C, iff the Given Graph is 3-Colorable by leaving UPTO 5 ...
2
votes
1answer
48 views

NP completeness of closest vector problem

Let $\mathcal{B} = \{v_1,v_2,\ldots,v_k\} \in \mathbb{R}^n$ be linearly independent vectors. Recall that the integer lattice of $\mathcal{B}$ is the set $L(\mathcal{B})$ of all linear combinations ...
3
votes
1answer
57 views

Hierarchy of complexity classes $\bigcup_{c > 0} \mathrm{Time}(2^{c \log^k n})$, w.r.t. $k$

This is a true/false question: For each integer $k > 1$, define the complexity class $\sf QP_k := \bigcup_{c > 0} Time(2^{c \log^k n})$. Then for all integers $k > 1$, $\sf QP_k ...
3
votes
1answer
107 views

Complexity Classes (P, NP) vs Language Hierarchies (REC, RE)

Is there any relation between the Complexity Classes (like P or NP) and Language hierarchies (like REC or RE) ? Form what I understand: (easy things are the things that can be done in polynomial ...
5
votes
2answers
77 views

Sensitivity and Block sensitivity

May be this question is really silly and obvious but I am missing something subtle. I am reading on Sensitivity and Block sensitivity. Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let ...
0
votes
1answer
40 views

Vertex Cover of size k in a tree?

What is a polynomial time algorithm for finding a vertex cover of size $k$ in a tree? Would depth first or breadth first search be efficient or is there some other algorithm that finds the vertex ...
1
vote
0answers
53 views

Sorting array with constant memory

Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell. So ...
0
votes
1answer
24 views

Can someone provide an introductory example of a certificate in complexity theory? [duplicate]

Just stepping into complexity theory, I am befuddled by this notion of a certificate and can't find any utility of this concept. From my understanding, a certificate is used when you are trying to ...
0
votes
0answers
34 views

A question on the BSS model with inequalities allowed

Let $k,M\in\Bbb N$ be fixed. In the BSS model we allow only $+,-,\times,=$ as valid operations and also an initial set of constants that are fixed for all instantiations of the algorithm. Here we ...
3
votes
1answer
32 views

Can someone explain in a simple way what “reducible” mean in complexity theory? [duplicate]

I find the word "reducible" used in complexity theory not very intuitive, and too general taken on a face value. What does it exactly mean by problem A reducible to B? Does it mean that A can be ...
1
vote
1answer
22 views

How does “language” relate to “problem” in complexity theory? [duplicate]

I am looking up the meaning of reduction in complexity theory: On Wikipedia it says: reduction is an algorithm for transforming one problem into another problem On the Princeton's notes on ...
2
votes
1answer
23 views

What is the implication of the sentence: “if any NP complete problem is p time solvable, then all problems in NP are p time solvable”

I find this quote here on page 13 Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p ...
2
votes
1answer
19 views

How to apply “verification” and “decision” for the SUBSET SUM problem?

The SUBSET SUM problem states that: Given finite set S of integers, is there a subset whose sum is exactly t? Can someone show me why verification is simpler ...
0
votes
0answers
36 views

Finding a rational non-zero of a multivariate polynomial in polynomial time

Suppose we have a degree $m$ multivariate polynomial $p(x_1, x_2, \ldots, x_m)$ in $n$ variables (by degree I mean the highest sum of powers of factors in any monomial term). Such a polynomial can ...
0
votes
0answers
33 views

Request for help with two reductions

Given two graphs one needs to decide if one of them has a subgraph isomorphic to the other. Given a subset of a graph one needs to decide if the induced subgraph is triangle free. Can someone ...
1
vote
0answers
25 views

Degrees of polynomials representing Boolean functions

Let $$B_1=\vee_{i_1=1}^d\wedge_{i_2=1}^d\dots\vee_{i_{2r-1}=1}^d\wedge_{i_{2r}=1}^dX_{i_1i_2\dots i_{2r-1}i_{2r}}$$ ...
-1
votes
1answer
43 views

Prove NP Complete

There are n numbers and we have to split the numbers into 2 sets such that difference of the sum of numbers of both sets is less than 100. Is this problem NP complete? Solution: I can prove that it ...