P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

6
votes
1answer
166 views

Integer linear programming in logarithmic number of variables

I read that integer linear programming is solvable in polynominal time if the number $n$ of variables is fixed, i.e. $n \in O(1)$. If the number of variables grows logarithmically, i.e. $n \in ...
-1
votes
1answer
88 views

Problems that are possibly not even exponential-time [on hold]

Many hard problems like the subset sum problem have easy and natural exponential-time algorithms. (It is not known whether there is a polynomial-time algorithm to solve this problem.) Are there ...
-3
votes
0answers
57 views

$A,B \in P \Rightarrow A \leq_p B$ [on hold]

"Complexity theory" is new to me. Today "polynomial-time reduction" was introduced and now I'm asking myself if the following is correct: $A,B \in P \Rightarrow A \leq_p B$ It might be simple, but ...
9
votes
2answers
126 views

Which graph problems are $W[1]$-Hard on directed(/weighted) graphs but FPT on undirected(/unweighted) graphs?

Following the equivalent questions regarding NP-Completeness (see the weight question and the directed question), I was wondering how parameterized problems are affected by these attributes. ...
-1
votes
0answers
57 views

EXP-Complete oracle separating P and NP [on hold]

Is there an $EXP-Complete$ oracle B which satisfies $P^B\neq NP^B$. Right now the only language $B$ i know which satisfies $P^B\neq NP^B$ is the one appearing in chapter 3 of "Computational ...
1
vote
0answers
71 views
+50

In domination perfect graphs is MDS certificate for MIDS?

I suspect this is wrong in case it makes sense at all. According to graphclasses: A graph is domination perfect if for every induced subgraph $H$ a minimum dominating set (MDS) has the same ...
5
votes
1answer
55 views

Quanitifier Free Presburger Arithmetic: Upper bound on solution size?

DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
4
votes
1answer
99 views

The relationship between completeness and strength of reductions

Ladner theorem can be stated as: $P \ne NP$ if and only if there exists an incomplete set in $NP-P$. Here an incomplete set is a set that is not complete for $NP$ under many-one polynomial time ...
6
votes
0answers
124 views

Evidence that Graph Isomorphism problem is not $NP$-complete

Graph isomorphism problem is one of the longest standing problems that resisted classification into $P$ or $NP$-complete problems. We have evidences that it can not be $NP$-complete. Firstly, Graph ...
2
votes
0answers
51 views

$\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ problems

All the problems which are either $\mathsf{APX}-\mathsf{Hard}$ and $\mathsf{MaxSNP}-\mathsf{Hard}$ cannot admit a $\mathsf{PTAS}$, unless $P=NP$. I would like to know whether $\mathsf{MaxSNP}$ ...
3
votes
1answer
69 views

What is the relationship between $\mathsf{APX}$ and $\mathsf{MaxSNP}$ classes?

My understanding of these classes is a really fuzzy. The more I am trying to read the more I am getting confused. Can anyone help me understand the relationship between these classes. More precisely, ...
3
votes
0answers
55 views

Implications of a deterministic polytime prime-finding algorithm

I'm wondering what are the current known uses/implications of a polynomial-time algorithm for the following problem: Given $n$ in binary, output a prime $p > n$. I'm both curious about ...
10
votes
2answers
178 views

What is the complexity of the equivalence problem for read-once decision trees?

A read-once decision tree is defined as follows: $True$ and $False$ are read-once decision trees. If $A$ and $B$ are read-once decision trees and $x$ is a variable not occurring in $A$ and $B$, ...
4
votes
1answer
101 views

Deciding whether the sum of independent random variables exceeds a threshold a majority of the time, PP-hard?

Say I have $n$ independent Bernoulli random variables, with parameters $p_1,\ldots,p_n$. Say, also, that I wish to decide whether their sum exceeds some given threshold $t$ with probability at least ...
1
vote
0answers
34 views

Computational complexity of Initial Value Problems of ODEs

Are there known results on computational complexity of initial value problems of ODEs? As my question may be somewhat vague, I want to mention that I'm mainly interested for results on the ...
6
votes
1answer
129 views

Integer factorization using polynomial whose roots are prime factors

Let $n$ be a square-free positive integer, let $n=p_{1}p_{2}\ldots p_{k}$ be the prime factorization of $n$ into $k$ distinct primes $p_{i}$. For such $n$, define ...
1
vote
0answers
102 views

Consequences of the existence of the following algorithm: does it imply any complexity class separation / collapse?

Let $G$ be a $3$-regular graph. Let $O$ be the number of vertex covers of $G$ having odd cardinality, and let $E$ be the number of vertex covers of $G$ having even cardinality. Let $\Delta = O - E$. ...
4
votes
1answer
151 views

Graph theoretic restriction to Proofs in Proof Complexity Theory

Proof complexity is a most basic area of computational complexity theory. An ultimate purpose of this area is to prove $NP\neq coNP$, that is, any prover cannot give a proof of unsatisfiability of ...
7
votes
2answers
657 views

Is square removal easier than factoring?

It seems to me that the square removal task can be reduced to the factoring task, but that there is no way to reduce factoring to square removal. Is there a way to make this "feeling" more precise, ...
0
votes
1answer
33 views

polytime transformation from a graph to a set of binary strings

$d_H$ denotes the Hamming distance between two binary strings of the same size. The problem is stated as follows. Given any undirected graph $(V, A)$, does there always exist a one-to-one ...
3
votes
3answers
193 views

Minimum vertex cover on k-regular graphs, for fixed k>2 NP-hard proof?

Good Evening! I am aware that the minimum (cardinality) vertex cover problem on cubic graphs ($3$-regular) graphs is $NP$-hard. Say positive integer $k>2$ is fixed. Has there been any ...
5
votes
1answer
131 views

Downward self-reducibility of factorization

Is integer factorization downward self-reducible? Is anything known about this?
2
votes
1answer
46 views

Promise Variant of Set-Packing

An instance of the SET-PACKING problem is given by a list of sets $\mathcal{S} = \{S_1,\dots,S_m\} \subseteq 2^U$. It is a ``yes'' instance iff there exists some subset $\mathcal S'$ of $\mathcal S$ ...
2
votes
1answer
70 views

Extractors in Practice: How to Determine the Min-Entropy in the Source Distribution

One of the main parameters in the construction of extractors is $k$, the min-entropy of the source distribution. In practice, suppose we want to extract randomness from a given source $S$. How do we ...
10
votes
0answers
187 views

Computing $\operatorname{MAJ}_n$ by $\operatorname{MAJ}_m$ in depth 2

Can the majority of $n$ bits be computed by a depth 2 formula all of whose gates compute the majority of $m$ bits where $m=O(n^c)$ for a constant $c<1$? Such a formula contains $m+1$ gates and ...
0
votes
1answer
79 views

How does one extend local checkability to quantum complexity classes?

How does one extend local checkability to quantum complexity classes like BQP? Or are quantum algortihms inherently holistic?
0
votes
1answer
121 views

Idea for a white-box PIT deterministic algorithm in polynomial time

Just a warning, I am an amateur and this algorithm probably doesn't work. A high level description of the algorithm: Be $f(x_1,...,x_n)$ a polynomial, $n$ the number of variables and $d$ is the ...
5
votes
0answers
78 views

Is the finite inverse semigroup isomorphism problem GI-complete?

Is the finite inverse semigroup isomorphism problem GI-complete? Here the finite inverse semigroups are assumed to be given by their multiplication tables.
4
votes
2answers
272 views

Is there a polynomial time algorithm for creating a set of vectors in general position?

It seems to be possible to create a set of vectors in $\mathbb{R}^n$ such that any subset of $n$ vectors forms a basis. For example, in $\mathbb{R}^3$, here is such a set with 21 vectors: $$ \left\{ ...
4
votes
2answers
282 views

Complexity class of sensitivity

Let $f:\{0,1\}^n\rightarrow \{0,1\}$ be a Boolean function. Let $[n]=\{1,2,\dots,n\}$. If $i\in[n]$, let $\Bbb 1_i$ be length $n$ vector with all $0$s except $1$ at $i$th position. If $B\subseteq ...
21
votes
1answer
457 views

Complexity of n-queens-completion?

The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions: $1\le Q[i] \le n$ for all $i$ $Q[i] \ne ...
3
votes
0answers
321 views

$NP$-complete problems on cubic Hamiltonian graphs

The class of cubic Hamiltonian graphs is well studied class. I came across the fact that independent set problem is $NP$-complete when restricting input to cubic Hamiltonian graphs. I am interested in ...
10
votes
1answer
184 views

Hartmanis-Stearns conjecture and the computable transcendental numbers

In the 1965 article "On the computational complexity of algorithms" by Hartmanis and Stearns, the authors conjecture that if a real-time Turing Machine computes the real number $r$ in, for example, ...
2
votes
1answer
132 views

Complexity of reversible Circuit Value

I am wondering what is known about the complexity of the reversible Circuit Value Problem (rCVP) and the corresponding reversible Satisfiability problem (rSAT). More precisely: a circuit ...
0
votes
0answers
65 views

Bijection between NP-complete problems

If $A$ and $B$ are NP-complete problems, is there a bijective function $f$ (computable in polynomial time) such that $w\in A$ iff $f(w)\in B$?
7
votes
0answers
116 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 ...
9
votes
1answer
298 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 ...
13
votes
1answer
293 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 ...
6
votes
0answers
240 views

Recognizing sequences sortable by transpositions?

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

How could God authenticate in one message? [closed]

        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
135 views

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

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 ...
7
votes
1answer
342 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
247 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
123 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
104 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
147 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
60 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 ...
5
votes
0answers
62 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
161 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 ...
10
votes
3answers
255 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 ...