P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

3
votes
0answers
46 views

Time complexity of a branching-and-bound algorithm

Theoretical computer scientists usually use branch-and-reduce algorithms to find exact solutions. The time complexity of such a branching algorithm is usually analyzed by the method of branching ...
-3
votes
0answers
30 views

Karp reduction/many-one reduction [on hold]

Why is Karp reduction also called "many-one reduction"? What do the 'many' and the 'one' stand for? I tried looking at wikipedia and read some books but I did not find any explantion. I do understand ...
0
votes
0answers
36 views

How many maximization algorithms can we run at the same time on a simple (or super) computer? [on hold]

I have a maximization problem which consists of finding the max of $2^L$ elements. This can be done in $O(2^L)$. This problem can be decomposed into $L$ maximization problems, where solving problem ...
5
votes
0answers
72 views

Quantum algorithms for QED computations related to the fine structure constants

My question is about quantum algorithms for QED (quantum electrodynamics) computations related to the fine structure constants. Such computations (as explained to me) amounts to computing Taylor-like ...
8
votes
1answer
119 views

“Snake” reconfiguration problem

While writing a small post on the complexity of the videogames Nibbler and Snake; I found that they both can be modeled as reconfiguration problems on planar graphs; and it seems unlikely that such ...
4
votes
0answers
85 views

Recognizing sequences sortable by transpositions?

While reading the post, Probability of generating a desired permutation by random swaps, by Scott, I got interested in this problem of sorting: Input: a sequence $A$ of $2N$ positive integers. ...
0
votes
3answers
288 views

How could God authenticate in one message?

        Thought experiment: Which data could convince experts, beyond reasonable doubts, about their origin outside our universe? From which margin should an expert consider such claim seriously? For ...
2
votes
0answers
120 views

Subset sum solver. Worth continue working on this method? [on hold]

I have been working in a subset sum problem solver for some time. The implementation is an exact/exhaustive search solver. The variable determining the asymptomatic growth rate is just $N$ (the ...
-2
votes
0answers
23 views

What is the relationship between regular, context free and computable language? [on hold]

Is there a diagram illustrating their relationships?
-4
votes
0answers
23 views

Quick question: What does it mean for a language to be “recognized” by an automaton? [on hold]

I am not particularly familiar with the usage of "recognized" in English, can explain what this means for a language be recognized by an automaton? Does it mean that the NFA, DFA, Pushdown or Turing ...
7
votes
1answer
312 views

Does $NP$-hardness of $c$-approximation (for some $c>1$) imply $APX$-hardness?

Assume that for a given minimization problem with only integer solutions, it is $NP$-hard to decide if the optimal solution is 5 or 6. I.e., a polynomial-time algorithm with an approximation ratio ...
14
votes
3answers
191 views

Can typed lambda calculi express *all* algorithms below a given complexity?

I know that the complexity of most varieties of typed lambda calculi without the Y combinator primitive is bounded, i.e. only functions of bounded complexity can be expressed, with the bound becoming ...
2
votes
1answer
103 views

The relationship between QCMA and QMA in the Turing and Communication model

First my background about computational complexity is still beginner. Recent paper published by Klauck and Podder [KP14] show that for the first time an exponential gap between computing partial ...
0
votes
2answers
99 views

Where can I find the proof of the theorem and what is the computational complexity of the computably isomorphic map?

"any two representations of reals which are acceptable are actually computably isomorphic",please see here for reference where may proof of this theorem be found, and what is the the computational ...
0
votes
1answer
90 views

Randomized Algorithm with random input

As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm ...
-2
votes
1answer
55 views

For two representations of finite length of one computable number are there $P$-time algorithms that compute one from another

Any computable number may have different representations of finite length . For example,$\sqrt{2}$ may be represented as root of equation, or as a (shortest for a universal Turing Machine)program of ...
4
votes
0answers
61 views

Can Iterative Compression lead minimization NP-hard problem to both in low complexity and good approximation?

The breakthrough theory of iterative compression introduced by Reed, Smith and Vetta [1] can give positive answers to a number of open problems of parameterized complexity of several important NP-hard ...
7
votes
2answers
134 views

Sensitivity-Block sensitivity conjecture - Implications

Let $f$ be a boolean function with sensitivity $s(f)$ and block sensitivity $bs(f)$. The Sensitivity-Block sensitivity conjecture conjecture states that there is a $c>0$ such that $\forall ...
0
votes
0answers
56 views

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

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 cyclic. What about to ...
10
votes
3answers
244 views

Is there a simple game with asymmetric complexity?

Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves. The usual ...
3
votes
1answer
82 views

Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
3
votes
0answers
25 views

APx hardness of Multiterminal Cut Problem

In a Multiterminal Cut problem input is a graph G=(V,E) and a set of k terminals T which is a subset of vertex set V. There is a weight w(e) associated with each edge in the graph. The question is to ...
-4
votes
0answers
42 views

NP problems whose optimization problems aren't polynomial time reducible

Can someone provide an example of an NP problem with an optimizational counterpart that can't be reduced to in polynomial time? I might have the definitions messed up, but here's an example. I read ...
1
vote
0answers
72 views

Are there NP-complete problems with quasi-polynomial expected time solutions?

I'm wondering if there exists an exact algorithm for some np-complete problem with quasi-polynomial time complexity. My best guess is 'no', because if there was one (with a reasonable C, not any C), ...
10
votes
1answer
411 views

For what c is division by c in AC0?

Suppose that our input is a binary $x$ and we have to output $\lfloor x/c \rfloor$, where $c$ is some constant integer. This is just a shift if $c$ is a power of two, but what about other numbers? Can ...
17
votes
1answer
129 views

Minimal cumulative set sum

Consider this problem: Given a list of finite sets, find an ordering $s_1, s_2, s_3, \ldots$ that minimizes $|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots$. Are there known algorithms ...
6
votes
2answers
575 views

Implications of Riemann Hypothesis variants in TCS

The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a ...
1
vote
0answers
72 views

Properties of “second-order” NP (complete) languages

Reading the question Natural NP-Complete Problems with Large Witnesses, I was interested in this language: $L = \{ \varphi ~~:~~ \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ ...
6
votes
0answers
47 views

Reconstructing labeled poset from linear extensions

Let $(P, <, \mu)$ be a labeled poset, that is, a partial order $(P, <)$ with a labeling function $\mu$ that maps the elements of $P$ to labels in an alphabet $\Sigma$. A label list (or word) is ...
5
votes
2answers
140 views

How many sets of vectors can be represented as the solutions of a Horn-SAT instance?

Let the solution space of a SAT instance be the set of Boolean vectors of satisfying assignments of $\{0,1\}$ to the variables (that result in the formula evaluating to TRUE). In other words, a ...
7
votes
1answer
176 views

What is the complexity of decision tree complexity?

Given a boolean function $f$ on $n$ bits, how hard is it to determine its decision tree complexity? (I assume the decision tree is simple, i.e., the allowed questions are the bits of the input.) If ...
0
votes
0answers
56 views

Understanding MA protocol as a variant of TM for small space setting

MA protocol is one of the most basic models of interactive proofs. Merlin is a prover sending a witness $w$ for given input string $x$, and Arthur is a verifier who verifies if $w$ is a positive ...
9
votes
2answers
166 views

Straight line complexity of monomials

Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$ we define $L(f)$ to be the straight-line complexity of $f$ over $k$. Let $F$ be the set of monomials of $f$, namely the ...
10
votes
2answers
209 views

How to judge the definition of computational complexity of reals is natural or suitable?

As we know, definition of computational complexity of algorithm is almost without controversy, but the definition of computational complexity of reals or the computation models over reals is not in ...
-2
votes
0answers
157 views

How to reduce the computational complexity max algorithm in this specific case

We work over $\mathbb{R}_+^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}_+^L$) a vector that ...
18
votes
0answers
377 views

Why is HAMILTONIAN CYCLE so different from PERMANENT?

A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment $\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
-1
votes
0answers
34 views

Reducing computational complexity of sorting algorithm in this specific case [duplicate]

We work over $\mathbb{R}^L$. Let $V$ be the set of column vectors whose coordinates take values $0$ or $1$. Thus, $V$ contains $2^L$ vectors. Let $\mathbf{w}(t)$ (in $\mathbb{R}^L$) a vector that ...
1
vote
1answer
80 views

Hitting set of very restricted linear forms

We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$. A hitting set $H\subseteq\mathbb{Z}^{n}$ for ...
0
votes
0answers
45 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have n cannisters that must go into m trucks that can each carry k cannisters. You require that no truck becomes overloaded, and for each cannister, there is a ...
20
votes
2answers
415 views

best known space lower bound for SAT?

Following on from a previous question, what are the best current space lower bounds for SAT? With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses ...
0
votes
2answers
151 views

Partition problem

We know that Partition problem is NP-complete: "Given a multi-set of positive integers like X = < a_1, a_2, ... a_n >, is there any bi-partition for X such that the summation of the numbers in S ...
1
vote
0answers
68 views

Implication of lower bounds in Boolean circuit to other models of computation

Suppose that one can prove that some hard function $f$ with $n$ bit input does not admit any Boolean circuit of size at most $n^t$. Then, how strong can we say about how hard $f$ is in other models? ...
7
votes
1answer
219 views

Is Kolmogorov complexity a surjective function?

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever). Define the Kolmogorov complexity ...
10
votes
1answer
309 views

Decide the existence of a string homomorphism

Consider the following problem: Given two strings x,y, decide whether there exists a string homomorphism f such that f(x)=y. It is easy to show that this problem is in $NP$. Are there other ...
1
vote
0answers
139 views

intuition that VP=?VNP is (not?) connected to P=?NP

recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1] what is ...
8
votes
1answer
178 views

A curious asymmetry in good characterizations

There are quite a few theorems, mostly in graph theory and combinatorial optimization, that are often referred to as good characterizations. They typically put a property in $NP\cap co-NP$, by showing ...
1
vote
1answer
92 views

Which factors make the problem of inferring the grammar difficult?

Scott Aaronson said in the paper entitled "Why Philosophers Should Care About Computational Complexity" (Please see ECCC Report: TR11-108, section 7, pp 25-31): Following the work of Kearns and ...
19
votes
0answers
502 views

Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?

The following question arose as a side product of some work I have been part of recently. An $m$ by $n$ $(0,1)$-matrix $M$ is partial circulant if it can be formed by taking the first $m$ rows of a ...
5
votes
1answer
220 views

Special case of Bin-packing problem

We know that the decision version of Bin-packing problem is NP-complete: Given an integer B, an integer k, and a list of integers X = (x1, x2, . . . , xn) where xi ∈ [0, B], is there any partition of ...
15
votes
0answers
393 views

Practically Good Algorithms of a Very Low Computational Complexity Class

I am looking for one (or more) examples of a parametric class of algorithms $P_t$ for approximately solving a class $\cal A$ of algorithmic questions with the following properties: 1) Solving the ...