P versus NP and other resource-bounded computation.

learn more… | top users | synonyms (1)

1
vote
1answer
40 views

Primitive Recursive Definition : Binary numbers

Usually primitive recursive functions are define from Zero, Identity and Successor, projectors, composition and recursion. But you obtain algorithms that works with unary numbers. For example, the ...
2
votes
0answers
49 views

Padding Arguments for Probabilistic Classes

Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or ...
-1
votes
0answers
42 views

Known time complexity advantage of quantum algorithms over classical algorithms [duplicate]

I know that this question may depend on how one formulates each complexity class, but in general, what time complexity advantage does quantum algorithms have over classical algorithms?
1
vote
0answers
88 views

Definition of Planar 3-SAT

What is the standard definition of Planar 3-SAT? I have seen a number of different definitions. What was the original paper that defined it and proved it to be NP-complete?
8
votes
0answers
67 views

NEXPTIME-completeness with more time for reductions

One thing that surprised me when learning about complexity theory is that for a complexity class C, we tend to define C-complete using polynomial time reductions, even when C is a very large ...
4
votes
0answers
143 views

Hardness of UNAMBIGUOUS-3DM

Let UNAMBIGUOUS-3DM be defined by analogy to UNAMBIGUOUS-SAT, i.e. as a promise problem version of three-dimensional matching where we may assume there is no more than one solution. Is there a ...
7
votes
0answers
89 views

How to find the “hard” probability distribution on the input for recursive boolean functions?

Background: Decision tree complexity or query complexity is a simple model of computation defined as follows. Let $f:\{0,1\}^n\to \{0,1\}$ be a Boolean function. The deterministic query complexity of ...
5
votes
0answers
51 views

Is graph coloring complete for poly-APX?

Is the graph coloring problem complete for poly-APX under C-reductions (alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
3
votes
1answer
113 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
4
votes
1answer
248 views

Reduction from SAT to 0,1 integer linear program with zero or one solutions

Probably this is well known. There is probabilistic reduction from SAT to Unique SAT (0 or 1 solutions). According to answer and comments derandomizing the reduction would imply $PH \subseteq \oplus ...
19
votes
0answers
300 views

$RL=L$ Progress Since 2006

Reingold, Trevisan, and Vadhan's breakthrough 2006 paper (http://dl.acm.org/citation.cfm?id=1132583) reduced the problem of showing $RL=L$ to producing pseudorandom walks on regular digraphs that are ...
10
votes
1answer
399 views

NP-complete problem with polynomially many certificates?

Let's call a language $L \in$ NP sparsely certificated if and only if: There exists a polynomial $p : \mathbb{N} \rightarrow \mathbb{N}$ such that for every input $x \in \Sigma^*$ of size $n$, if $x ...
-2
votes
0answers
68 views

Laplace's Demon [closed]

Can we apply Laplace's Demon anywhere in theoretical computer science? Laplace's Demon talks of an "all-knowing intellect" at a universal level, isn't it possible to apply the same to any ...
-1
votes
0answers
59 views

“Simple” algorithm for 1x1 sliding blocks

I'm working on a problem involving a type of sliding block game, and stumbled upon apaper of Hearne and Demaine where they introduced the "Nondeterministic Constraint Logic" machine as a framework for ...
2
votes
1answer
204 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u ...
2
votes
1answer
181 views

Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$

I'm in search for examples of decision problems lying in $\text{PSPACE}\cap \text{coNP-hard}$ which are also not (known to be) in $\text{coNP}\cup \text{NP}\cup \text{NP-hard}\cup ...
-2
votes
0answers
71 views

Deterministic Polynomial Time Algorithm for PIT? [closed]

I think I have found such an algorithm, it is based on a simple fact: Given the polynomial we are testing $p$ with $n$ variables and arithmetic circuit size $m$ and a point $\vec x$ where $p(\vec ...
5
votes
2answers
116 views

Is there an oracle separating Parity-P from PSPACE?

Is $ (\oplus \mathsf{P})^A \not \supseteq \mathsf {PSPACE}^A$ for some language $A$?
12
votes
1answer
528 views

A course for learning algebraic complexity

I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT. Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
-1
votes
0answers
60 views

In what complexity classes other than $NP$ are these problems related to unary languages?

If I remember correctly saw this reduction in a paper can't find at the moment. Consider the following NP-complete variation of the Subset Sum problem. Given a set of positive integers ...
0
votes
1answer
151 views

Would derandomizing the reduction from SAT to Unique SAT imply $NP$ and $coNP$ are in $\oplus P$?

The Unique SAT problem (USAT) is to determine whether a given formula has a satisfying assignment, when we are guaranteed that it has at most one satisfying assignment. By a theorem ...
4
votes
1answer
188 views

Why is computing pure Nash equilibria NP-complete?

In this paper, it is claimed that computing pure-strategy Nash equilibria of games in standard normal form is NP-complete. This confuses me, because I do not understand why it is hard to guess the ...
13
votes
1answer
230 views

Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory. Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of ...
3
votes
0answers
43 views

Interpolating the Tutte polynomial at the values of two hyperbolas

In a MO question basically I asked when the Tutte polynomial of planar graph can be uniquely determined by the polynomially computable values at the special points and at the two hyperbolas. The ...
7
votes
1answer
152 views

Problems in AM or in MA

What are the examples of problems known to be in $\mathsf{AM}$ (resp. $\mathsf{MA}$) which are not known to be in $\mathsf{NP}$ nor in $\mathsf{BPP}$? For $\mathsf{AM}$, I know the following two ...
1
vote
1answer
129 views

Density of answers for NP complete problems?

There is a result which goes along the lines of: Definition: For every language $L$, define $L_n = \{ w \in L \mid \text{length}(w) = n \}$, i.e. the subset of $L$ of words whose length is $n$. ...
7
votes
0answers
131 views

Implications of the impossibility of efficient sampling from random non-Hamiltonian graphs

Nisan's answer to this question shows the Impossiblity of efficient sampling from random non-Hamiltonian graphs (unless $NP=coNP$). I am interested in the implications of this conjecture. Does the ...
8
votes
1answer
715 views

What is the axiomatic (set theory) context of the P vs NP and NP=EXPTIME conjectures?

When the conjecture $\mathbf{P} = \mathbf{NP}$ or $\mathbf{P} \neq \mathbf{NP}$ is set (e.g. by the Clay Mathematical Institute by S. Cook, see here) what mathematical axiomatic system is assumed? In ...
-4
votes
0answers
38 views

I am undergraduate in CS with a fledgling interest in TCS [on hold]

Please suggest some fun, upbeat books to understand the basics of TCS. I am reasing a book on reinforcement algorithms and taking a course on Machine learning, but feel like I need to know the basics ...
6
votes
0answers
91 views

Confusion about reduction counting vertex covers to counting cycle covers

This confuses me. One easy case of counting is when the decision problem is in $P$ and there are no solutions. A lecture show that the problem of counting the number of perfect matchings in a ...
3
votes
0answers
58 views

Probability distributions and computational complexity

Some probability distributions are easier to work with than others. Consider the following two problems. Given a number $n$, return $i$ with $0 \leq i < n$ with uniform probability, i.e. ...
9
votes
1answer
219 views

Hidden path in square grids

I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete. Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ ...
5
votes
3answers
204 views

Candidates for One-Way Function

Why are the candidates for one-way functions so few? Today, almost all candidates are based on elementary mathematics, except Goldreich's candidate 2000 and ... (?!). Why one can not generate ...
7
votes
3answers
191 views

Is there a generalization of information theory to polynomially knowable information?

I apologize, this is a bit of a "soft" question. Information theory has no concept of computational complexity. For example, an instance of SAT, or an instance of SAT plus a bit indicating ...
6
votes
0answers
80 views

What is known about reduction by “$P_1$ interprets $P_2$” for generalized programming languages?

Inspired by this answer, let's say that a programming language is given by the data $L=(P,ev)$ where $P$ (the set of "valid programs") is a computable subset of $\Sigma^*$ and $ev$ (the "evaluator") ...
8
votes
0answers
109 views

Collapsing PH Implications

It seems that many results in complexity hold assuming PH doesn't collapse to the second or third levels. At these low levels, I have some intuition about the collapse not occurring since additional ...
4
votes
0answers
74 views

How many exponentiations can the Shamir algorithm reduce?

The Shamir's algorithm is depicted as follows (cited from Handbook of Applied Cryptography, chapter 14, algorithm 14.88, page 618) Shamir's algorithm INPUT: group elements $g_0,g_1,\dots, g_{k-1}$ ...
0
votes
0answers
70 views

Computational complexity of generating all stack-sortable permutations of $n$ numbers

What is the computational complexity of an algorithm that generates all stack-sortable permutations of $n$ numbers?
-1
votes
0answers
28 views

Trees, and how to organize data and answer queries efficiently

Suppose there exists a set $X$, containing zero or more elements of some type, and we'd like to run a query, as efficiently as possible. For many interesting queries - value associated with a key, ...
-1
votes
1answer
97 views

What can we say about all cycles in graphs (connected undirected graph)

I am considering one optimization problem who is known to be NP hard in the general setting. But there is application of this problem on the cylces of graph. This problem involves several sets and ...
4
votes
0answers
108 views

Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices. What is the complexity of edge coloring ...
5
votes
1answer
146 views

The Overfull conjecture in graph theory and $coNP$

I am not good at complexity, but got a possible relation between a plausible conjecture in graph theory and $coNP$. Graph $G$ is Class 1 if it can be edge colored with $\Delta(G)$ colors, otherwise ...
0
votes
1answer
200 views

Complexity Theory in Finance and journals?

What journals are there that try to combine these two areas ? I came across the Algorithmic Finance Journal, are there others ? Looking at papers, mixed to overly -ve views about the quality and ...
6
votes
0answers
76 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
7
votes
4answers
445 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems ...
2
votes
1answer
113 views

Is there an additive time hierarchy theorem?

I would like something like this to be true: Conjecture: There is a function $g(n)$ such that for all functions $f(n)$ (perhaps satisfying some reasonable properties, like time-constructability), ...
4
votes
1answer
126 views

$\ell_1$ norm of Fourier coefficients vector for the hypercube

Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$. Given a ...
3
votes
1answer
64 views

Commitment schemes with verification in NC0

Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$? If so, what is the minimum possible depth of the circuit for verification? Applebaum ...
7
votes
0answers
296 views

Assigning probability to membership in an NP-complete language

Motivation Assuming $\mathsf{P}\ne\mathsf{NP}$, it is impossible to efficiently decide membership in an NP-complete language. I would like to assign probability to such membership, in some sense. ...
16
votes
3answers
2k views

P and NP classes explanation through lambda-calculus

In the introduction and explanation P and NP complexity classes often given through Turing machine. One of the model of computation is the lambda-calculus. I understand, that all of models of ...