Questions related to the (computational) complexity of solving problems

learn more… | top users | synonyms (2)

3
votes
1answer
28 views

Minimal complexity for pairing two comparable sets with comparability restrictions

A project at university (whose deadline has passed by now) presented the following problem: Consider two finite sequences of (not necessarily distinct) real numbers $a_1,\ldots,a_n$ and ...
4
votes
1answer
49 views

What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

I'm having trouble understanding the definitions for complexity classes in the arithmetic heirarchy, and because of the naming schemes, "Googling" things is somewhat difficult. Can anyone provide me ...
0
votes
1answer
27 views

Concise way to say “increases with n or some term of n”

I'm writing a thesis proposal and one of the systems involved has unknown complexity. It's not a focus of the proposal, but I wanted to include a line like this, as speculation: Presumably the ...
1
vote
1answer
69 views

Cycle of length k with no repeated edges

I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with ...
2
votes
0answers
28 views

Overlap between fields in CS

I hope this isn't too meta. I have finally had some serious graduate-level exposure to CS Theory and loved it. I really enjoyed complexity theory (time and space complexity, the different classes, ...
3
votes
0answers
66 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
1
vote
1answer
20 views

The significance of bounded parameters in complexity

A lot of complexity results are given with respect to bounded cases where results are more favourable. For example, the graph isomorphism problem — which is GI-complete in general — is known to be ...
2
votes
1answer
36 views
+50

Characterizing the range of a polytime function

Is it true that an infinite language is in P iff it is the range of a length increasing polytime function? I ask because I know that it is a basic result in computability theory that a set is ...
0
votes
0answers
63 views

Clique and its algorithm

The problem: Input: A graph $G=(V,E)$ and a number $k$ Question: Does G have a k-clique, i.e. a complete subgraph of k vertices? If we were suppose to solve, the function problem that a given graph ...
6
votes
2answers
73 views

Is $NP$ “minimal”, i.e. does $\Pi\notin NP$ imply $\Pi$ is $NP$-hard?

Suppose $\Pi$ is a decidable decision problem. Does $\Pi\not \in NP$ imply $\Pi$ is $NP$-Hard? Edit: if we assume there exists $\Pi\in coNP\setminus NP$ then we are done. Can we refute the claim ...
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
39 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
32 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
262 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
44 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
23 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. ...
9
votes
3answers
873 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 ...
1
vote
0answers
24 views

Polynomials and permanent/determinant [migrated]

Let $f\in \Bbb Z[x_1,\dots,x_n]$ be a multivariate polynomial. Is it possible to represent $f$ say of TOTAL degree $d$ by a $({dc})^{n}\times ({dc})^{n}$ determinant or $({dn})^c\times ({dn})^c$ ...
0
votes
1answer
38 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
258 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
41 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
136 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
87 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
28 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
63 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
23 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
74 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
90 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
23 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
163 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
34 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
55 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
88 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
140 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
36 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
56 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
26 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
28 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
17 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 ...
2
votes
1answer
36 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
45 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
56 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
74 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
74 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
38 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 ...