P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

2
votes
0answers
44 views

When is $FP^{NP[f(n)]}$ the same as $FP^{NP}$?

I am very confused, so this might not make sense. I am following the exposition in the polynomial hierarchy chapter of Papadimitriou's textbook. We are in the function-problem world. The problem ...
8
votes
1answer
132 views

Randomized Polynomial Hierarchy?

I wonder, what would happen, if in the definition of $PH$ (Polynomial Hierarchy, see, e.g., here), the role of $NP$ would be replaced by $RP$? It seems, we could still build a hierarchy, the same ...
-1
votes
0answers
21 views

understanding the definition of L-reduction of NPO problems

I read the definition of L-reduction in wiki https://en.wikipedia.org/wiki/L-reduction. I am trying to see if the following can be taken as definition of L-reduction. Also please suggest some books ...
5
votes
2answers
159 views

Completeness under injective Karp reductions

Karp reduction is polynomial time computable many-one reduction between two computational problems. Many Karp reductions are actually one-one functions. This raises the question whether every Karp ...
3
votes
2answers
142 views

Graph coloring/partitioning problem

I'm interested in the complexity of the following problem: Problem P: Given an undirected graph $G=(V,E)$ and a weight function $w: E \rightarrow \mathbb{R}$ (so weights can be negative, too), color ...
8
votes
0answers
113 views

Knot Recognition as a Proof of Work System

Currently bitcoin has a proof of work (PoW) system using SHA256. Other hash functions use a proof of work system use graphs, partial hash function inversion. Is it possible to use a Decision problem ...
-2
votes
1answer
118 views

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

$\mathsf{P/Poly}$ captures those problems that could be solved in polynomial time given some precomputed polynomial number of constants. Is there an analogous complexity class in randomized world ...
-3
votes
1answer
147 views

Consequences of polynomial time algorithm to variant of integer factorization

Given $N,U,V\in\Bbb N$ is there $n\in[U,V]\cap\Bbb N$ such that $n|N$ is $\mathsf{NP}$-complete modulo Cramer's conjecture on prime gaps is shown in An NP-complete variant of factoring. So supposing ...
1
vote
0answers
169 views

Convex hull of polytopes

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; ...
5
votes
0answers
64 views

Question about a unary language construction

For any language $L$, let us define another language $Tally(L)$, as follows: $$Tally(L)=\{1^n\;|\;\exists x \;\mbox{with}\; x\in L \;\mbox{and}\; |x|=n\}$$ That is, $Tally(L)$ encodes whether there is ...
1
vote
1answer
98 views

Assignment of values for a set

Consider the following problem: Input: the vertices of two $n$ dimensional axis-parallel cubes: $\times_{i=1}^{n} [a_i,b_i] \subseteq [0,1]^n$ and $\times_{i=1}^{n} [l_i,u_i] \subseteq [0,1]^n$. ...
-1
votes
1answer
165 views

What is the simplest known solver for a np-complete problem?

Lets define the simpler of two terms as the one with shortest description length on the untyped λ-calculus. Trying to find the simplest solver for a np-complete problem, I've got this: ...
10
votes
0answers
111 views

To what extent, computational ability for hard tasks helps in solving easy tasks

In short, the question is: to what extent, computational ability for hard tasks really helps you in solving easy tasks. (There could be various ways to make this question interesting and non-trivial, ...
5
votes
1answer
151 views

Complexity of k-clique for hypergraphs

Classic Problem: Let a number $k$ be given. The $k$-clique problem is as follows. Given a graph $G$, does there exist a subset $S$ of $k$ vertices so that any two vertices of $S$ are adjacent? ...
2
votes
0answers
75 views

Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
-1
votes
1answer
86 views

FPT algorithm equivalent definitions [closed]

On this page, the definition of a Fixed-Parameter Tractable algorithm is given, followed by the very classical example, Vertex Cover. But how the complexity given for Vertex Cover, $O(kn+1.274^k)$ ...
11
votes
1answer
169 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
3
votes
0answers
67 views

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting ...
4
votes
1answer
88 views

Polytopes convex hull

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
8
votes
1answer
152 views

What is largest class of functions $C$ such that we know $\#P$ in not contained in $C$-generated $TC^0$?

In [1] it is stated that "It remains an open question as to whether every function in $\#P$ has $TC^0$ circuits (although it is at least known that not all $\#P$ functions have DLogTime-uniform ...
4
votes
0answers
191 views

Bit complexity of modulo operations?

We know that using FFT we can compute multiplication of an $a$ bit number with a $b$ bit number in $(a+b)^{1+\epsilon}$ time. My question is supposing we want to compute $A\bmod B$ where $A$ is an ...
6
votes
1answer
271 views

A question on GCT

In paper 'On vanishing of Kronecker coefficients' here in http://arxiv.org/pdf/1507.02955v1.pdf, it is showed that deciding positivity of kronecker coefficients is in general NP hard. However there is ...
18
votes
4answers
521 views

What evidence is there that Graph Isomorphism is not in $P$?

Motivated by Fortnow's comment on my post, Evidence that Graph Isomorphism problem is not $NP$-complete, and by the fact that $GI$ is a prime candidate for $NP$-intermediate problem (not $NP$-complete ...
2
votes
1answer
71 views

H-representation of convex hull

Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows: $P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
1
vote
1answer
131 views

How does one determine if a mixed bipartite quantum state is entangled or not?

My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf Mathematically one can think of being given a ...
8
votes
1answer
171 views

What is the smallest class of reductions under which there is a $\mathsf{P}$-complete problem?

It is common to define $P$-completeness with respect to log-space many-one reductions. I am looking for a complexity class $C \subseteq \mathsf{L}$ such that there are $\mathsf{P}$-complete problems ...
2
votes
1answer
138 views

Would a proof that the traveling salesman algorithm can't be encoded on LAL also prove P!=NP?

An answer to the traveling salesman (and similar) problems can be easily verified on light lambda-calculi. Also, if I understand correctly, the light lambda-calculi can compute every polinomial-time ...
0
votes
0answers
134 views

NP-hardness of minimizing sum of complicated objective function

In our research, we faced the following problem optimization problem: Input: a list of $k$ pairs of positive integers $(n_1,d_1), \ldots, (n_k,d_k)$; an integer $m$. Output: $P$, a partition of the ...
4
votes
1answer
216 views

Evidence that UniqueSat is dense

UniqueSAT ={$\phi$| $\phi$ has unique satisfying assignment } represents an important class of computational problems. Unique SAT is CoNP-hard and $US$-complete. What is the density of UniqueSAT? ...
4
votes
1answer
149 views

What do you call the join of two optimization problems?

I have two optimization problems, both of whose inputs are from the set $I$ and whose solutions are from the set $S$, one a minimization with objective function $m_{\min}$ and one a maximization with ...
19
votes
0answers
328 views

What is the power of general poly-size permutation branching programs?

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
4
votes
0answers
167 views

A SAT related question

Given a sequence of $n$ propositional formulas $\varphi_1, \cdots, \varphi_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$. Define $K=\min\{k\mid \wedge_{i=k}^n \varphi_i\not\models ...
18
votes
3answers
466 views

Computation of reals: floating point vs TTE vs domain theory vs etc

Currently, computation of reals in most popular languages is still done via floating point operations. On the other hand, theories like type two effectivity (TTE) and domain theory have long promised ...
3
votes
1answer
346 views

If BQP contains NP, does this mean that P=NP?

There is a question raised by Scott Aaronson in one of his papers [1]: "Could we show that if NP ⊆ BQP, then the polynomial hierarchy collapses?". Assuming the answer is yes, and it is also know that ...
7
votes
2answers
165 views

Lexicographically minimal topological sort of a labeled DAG

Consider the problem where we are given as input a directed acyclic graph $G = (V, E)$, a labeling function $\lambda$ from $V$ to some set $L$ with a total order $<_L$ (e.g., the integers), and ...
0
votes
1answer
158 views

Is longest common subsequence with bounded occurrences NP-complete?

The general longest common subsequence problem (LCS) over a binary alphabet is NP-complete. Does the problem remain NP-complete if each input string has m zeros and n ones, where m and n are ...
4
votes
1answer
128 views

Is SAT with two “opposite” solutions NP-hard?

Here is a variant of the SAT problem in which a satisfying assignment must have additional properties. Input: A 3-CNF formula $f$ with variables $x_{1\dots k}$. Output: For an assignment $S$ of ...
6
votes
0answers
124 views

Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?

The standard problem 1-in-3 SAT (or XSAT or X3SAT) is: Instance: a CNF formula with every clause containing exactly 3 literals Question: is there a satisfying assignment setting precisely 1 literal ...
1
vote
1answer
165 views

Two paper appear to imply collapse via coloring $P_5$-free graphs

Found this from graphclasses.org. Two papers give conflicting results for coloring $P_5$-free graphs which appear to imply $P=NP$. From Polynomial-time algorithm for vertex k-colorability of ...
2
votes
1answer
140 views

Lookup complexity in augmented interval tree

If we consider the following problem: Stream of intervals, coming in one at a time, which we maintain in an augmented interval tree (Interval tree). At some point in time later, we get a point, and ...
8
votes
2answers
167 views

Computed circuit complexity of decision problems

Has anyone explored what is the circuit complexity of classic decision problems such as Primes or Graph-Isomorphism for small input size $N$? While most people are interested in the how the scaling ...
7
votes
1answer
180 views

Algorithms for printing the digits of pi, minimizing the time spent between digits

What is the smallest function $t(n)$ such that there exists an algorithm which prints the binary digits of $\pi$, with the time spent between printing digit $n - 1$ and digit $n$ being $O(t(n))$? ...
2
votes
3answers
114 views

Heuristic with worst-case exponential complexity

I have been working with some colleagues on a metaheuristic for an NP-Hard optimization problem. It is a genetic algorithm using a steady-state population replacement strategy (at each iteration a ...
8
votes
1answer
207 views

Canonical representation of Binary Decision Tree in Ptime?

I am wondering whether there may exist a way to give a sort of "normal form" for binary decision trees (BDT) in a tractable way. More precisely: a BDT is a tree with internal nodes labelled by ...
2
votes
1answer
150 views

Complexity of simple undirected graph isomorphism problem

We define a simple undirected graph as a graph where no vertex has a loop and there is only zero or one undirected, unweighted edge between any pair of vertices. My question: What is the complexity ...
6
votes
2answers
173 views

P-complete decision problems about integers

Are there any known examples of P-complete decision problems which take as input a single integer? (non-unary, as unary feels like un-naturally forcing the issue) It feels like there are many ...
3
votes
0answers
72 views

Are there works on function complexity classes not included in FNP? [closed]

Is there a sort of polynomial hierarchy in the case of function problems?
1
vote
2answers
170 views

Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand. In Diffie-Hellman Alice and Bob ...
2
votes
0answers
61 views

Is joint Kolmogorov Complexity order invariant?

Due to the symmetry of information, it follows up to an additive constant that K(X,Y) = K(Y,X) Does this hold for more than two data objects as well?
3
votes
2answers
240 views

What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?

As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?