Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROMISE PROBLEMS:
Reports tagged with promise problems:
TR97-031 | 9th September 1997
Oded Goldreich

#### On the Limits of Non-Approximability of Lattice Problems

Revisions: 2

We show simple constant-round interactive proof systems for
problems capturing the approximability, to within a factor of $\sqrt{n}$,
of optimization problems in integer lattices; specifically,
the closest vector problem (CVP), and the shortest vector problem (SVP).
These interactive proofs are for the coNP direction'';
that is, ... more >>>

TR03-011 | 17th February 2003
Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang

#### Disjoint NP-Pairs

We study the question of whether the class DisNP of
disjoint pairs (A, B) of NP-sets contains a complete pair.
The question relates to the question of whether optimal
proof systems exist, and we relate it to the previously
studied question of whether there exists ... more >>>

TR07-005 | 17th January 2007
Rahul Santhanam

#### Circuit Lower Bounds for Merlin-Arthur Classes

We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For ... more >>>

TR14-136 | 17th October 2014
Viliam Geffert, Abuzer Yakaryilmaz

#### Classical Automata on Promise Problems

Promise problems were mainly studied in quantum automata theory. Here we focus on state complexity of classical automata for promise problems. First, it was known that there is a family of unary promise problems solvable by quantum automata by using a single qubit, but the number of states required by ... more >>>

TR16-183 | 16th November 2016
Joshua Brakensiek, Venkatesan Guruswami

Revisions: 1

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints $\Gamma$ consists of a pair $(\Psi_P, ... more >>> TR18-059 | 6th April 2018 Joshua Brakensiek, Venkatesan Guruswami #### Combining LPs and Ring Equations via Structured Polymorphisms Revisions: 1 Promise CSPs are a relaxation of constraint satisfaction problems where the goal is to find an assignment satisfying a relaxed version of the constraints. Several well known problems can be cast as promise CSPs including approximate graph and hypergraph coloring, discrepancy minimization, and interesting variants of satisfiability. Similar to CSPs, ... more >>> TR19-053 | 5th April 2019 Andrei Krokhin, Jakub Opršal #### The complexity of 3-colouring$H$-colourable graphs We study the complexity of approximation on satisfiable instances for graph homomorphism problems. For a fixed graph$H$, the$H$-colouring problem is to decide whether a given graph has a homomorphism to$H$. By a result of Hell and Nešet?il, this problem is NP-hard for any non-bipartite graph$H$. In ... more >>> TR19-094 | 16th July 2019 Venkatesan Guruswami, Sai Sandeep #### Rainbow coloring hardness via low sensitivity polymorphisms A$k$-uniform hypergraph is said to be$r$-rainbow colorable if there is an$r$-coloring of its vertices such that every hyperedge intersects all$r$color classes. Given as input such a hypergraph, finding a$r$-rainbow coloring of it is NP-hard for all$k \ge 3$and$r \ge 2\$. ... more >>>

TR20-004 | 17th January 2020
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivny

#### The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs

In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "weak," and in the associated decision problem one must distinguish between being able to satisfy all the strict constraints versus not ... more >>>

ISSN 1433-8092 | Imprint