Papers for Graduate Seminar 238900-13
Papers for Graduate Seminar 238900-13
Advertizing BSS
-
BCSS-chapter6.pdf
* Algebraic settings for the problem $P\neq NP$?"
L. Blum, F. Cucker, M. Shub and S. Smale
Preprint of Chapter 6 of [BCSS].
-
ShubSmale-pap97.pdf
On the intractability of Hilbert's nullstellensatz
and an algebraic version of $NP \neq P$?"
M. Shub and S. Smale
Smale's collected work, Paper from 1997
-
fea-blum.pdf
(Published version, Notices of AMS, 2004)
TuringMeetsNewton.pdf
(offprint with more pictures)
* Computing over the Reals: Where Turing Meets Newton
Leonore Blum
-
Meer-Michaux-survey.pdf
* A survey on real structural complexity theory
K. Meer and C. Michaux
Bulletin of the Belgian Mathematical Society, 1997
-
Novak-JC-1995.pdf
* The Real Number Model in Numerical Analysis
E. Novak
Journal of Complexity 11 (1995) 57-73
Abstract: Gives an alternative definition of BSS.
Combinatorial problems as sets of polnomial equations
-
Margulies-phd.pdf
Computer Algebra, Combinatorics, and Complexity: Hilbert's
Nullstellensatz and NP-complete Problems,
Susan Margulies
Ph. Thesis, 2008
-
MarguliesHicks.pdf
An Algebraic Exploration of Dominating Sets
and Vizing's Conjecture
S. Margulies and I.V. Hicks
Preprint, 2011
-
LoeraLeeMalkinMargulies.pdf
Computing infeasibility certificates for combinatorial
problems through Hilbert's Nullstellensatz
J. A. De Loera, J. Lee, P. N. Malkin, S. Margulies
Journal of Symbolic Computation 46 (2011) 1260-1283
-
Koiran-JC-1996.pdf
* Hilbert's Nullstellensatz is in the Polynomial Hierarchy
P. Koiran
Journal of Complexity, 12, 273-286 (1996)
Abstract: Studies the complexity of Hilbert's Nullstellensatz
in the discrete setting. Shows it is in $PH$.
Note in BSS it is $NP_R$-complete and $NP_C$-complete.
-
Koiran-JC-2000.pdf
* On the complexity of local dimension for constructible sets
P. Koiran
Journal of Complexity, 16, 311-323 (2000)
Abstract: $NP_C$-completeness of existence of irreducible components of dimension $d$.
P vs NP over general structures
-
Mainhardt-JSL-2004.pdf
P versus NP and Computability Theoretic Constructions in Complexity Theory over Algebraic
Structures
Gunther Mainhardt
Journal of Symbolic Logic, 2004
Abstract:
Over structures, described below, we have two kinds of nondeterminism:
A first kind, $N_1P$, which corresponds to the situation that we have finitely many choices
for the next computation step and a second kind, $N_2P$, which consists of guessing an
element of the structure.
We show that there is a structure of countably infinite signature with $P = N_2P$ and a
structure of finite signature with $P = N_1 P$ and $N_1 P \neq N_2P$.
We give a further example of a structure of
finite signature with $P \neq N_1P$ and $N_1P \neq N_2P$.
-
Prunescu-JSL-2002.pdf
A Model-Theoretic Proof for $P \neq NP$ over All Infinite Abelian Groups.
Mihai Prunescu,
Journal of Symbolic Logic, 2002
Abstract:
We give a model-theoretic proof of the fact that for all infinite Abelian groups
$P \neq NP$ in
the sense of binary nondeterminism. This result has been announced 1994 by Christine GaBner.
Introduction.
-
Prunescu-JSL-2006.pdf
Structure with Fast Elimination of Quantifiers
Mihai Prunescu
Journal of Symbolic Logic, 2006
Abstract:
A structure of finite signature is constructed so that the structure satisfies
the relativized model-theoretic version of $P=NP$.
-
Meer-JC-1992.pdf
* Real Number Models under Various Sets of Operations
Klaus Meer
Journal of Complexity , 1992
-
Prunescu-JC-2000.pdf
* $P \neq NP$ for the Reals with various Analytic Functions
Mihai Prunescu
Journal of Complexity , 2000
Abstract:
We show that non-deterministic machines in the sense of [BSS]
defined over wide classes of real analytic structures are more powerful
than the corresponding deterministic machines.
-
Ziegler-APAL-2012.pdf
Real computation with least discrete advice: A complexity theory of
nonuniform computability with applications to effective linear algebra
Martin Ziegler
Annals of Pure and Applied Logic, 2012
-
Rybalov-TCS-2004-.pdf
* On the $P=NP$ problem over real matrix rings
A. Rybalov
Theoretical Computer Science, 2004
Abstract:
We prove that that $P\neq NP$ over real
matrix rings.
Between P and NP
-
MalajovichMeer-np.pdf
On the structure of $NP_C$
G. Malajovich and K. Meer
SIAM J. Comput. 28(1): 27-35 (1998)
-
BenDavid-Meer-Michaux.pdf
* A Note on Non-complete Problems in $NP_R$
S. Ben-David, K. Meer and C. Michaux
Journal of Complexity, 16, 324-332 (2000)
-
Meer-Ladner-InfComp-2012.pdf
On Ladner's result for a class of real machines with restricted
use of constants
Klaus Meer
Information and Computation 210 (2012) 13-20
Reals with addition and order
-
Hodes-1971.pdf (Conference version)
,
Hodes-ArtInt.pdf (Journal version)
Solving Problems by Formula Manipulation
in Logic and Linear Inequalities
Louis Hodes
IJCAI 1971: 553-559.
Artif. Intell. 3(1-3): 165-174 (1972)
-
ferranterackoffrealaddition.pdf
* A decision procedure for the first order theory
of real addition with order
Jeanne Ferrantet and Charles Rackoff
SIAM J. COMPUT. Vol. 4, No. 1, March 1975
-
Koiran-TCS-1994.pdf
Computing over the reals with addition and order
P. Koiran
Theoretical Computer Science 133 (1994) 35-47
-
Cucker-Koiran-JC-1995.pdf
* Computing over the reals with addition and order: Higher complexity classes
F. Cucker and P. Koiran
Journal of Complexity, 11 (1995)
-
Monniaux-2008.pdf
A Quantifier Elimination Algorithm for Linear Real Arithmetic
David Monniaux
LPAR 2008, LNCS 5330, pp. 243?257, 2008
-
Nipkov-2008.pdf
Linear Quantifier Elimination
Tobias Nipkow
IJCAR 2008, LNCS 5195, pp. 18?33, 2008
Polynomial Hierarchy in BSS and Beyond
-
Meer-TCS-2000.pdf
* Counting Problems over the Reals
K. Meer
TCS 242.1-2 (2000) 41-58
Abstract: Inroduces counting complexity over the reals.
-
BuergisserCucker-STOC-2004.pdf
Counting Complexity Classes for Numeric Computations II: Algebraic and Semialgebraic Sets
P. Buergisser and F. Cucker
STOC, 2004
-
BuergisserCuckerLotz-FoCM-2005.pdf
Counting Complexity Classes for Numeric Computations. III: Complex Projective Sets
P. Buergisser and F. Cucker and M. Lotz
Found. Comput. Math. 351?387 (2005)
-
BasuZell-2010.pdf
Polynomial Hierarchy, Betti Numbers,
and a Real Analogue of Toda's Theorem
Saugata Basu and Thierry Zell
Found Comput Math (2010) 10: 429-454
-
Basu-2012.pdf
A Complex Analogue of Toda's Theorem
Saugata Basu
Found Comput Math (2012) 12:327-362
-
alc-final.pdf
* A Computational Framework for the Study of Partition
Functions and Graph Polynomials
T. Kotek, J.A. Makowsky and E. Ravve
to appear in the Proceedings of the 3rd Asian Logic Conference, 2011
Critique on BSS
Recursion Theory in BSS
-
MichauxTroestler-TCS-2000.pdf
* Isomorphism Theorem for BSS Recursively Enumerable Sets over Real Closed Fields
C. Michaux and C. Troestler
TCS 231 (2000) 253-273
-
Zhong-TCS-1998.pdf
* Recursively enumerable subsets of $R^q$ in two computing models
Blum-Shub-Smale macine and Turing machine
Ning Zhong
TCS 197 (1998) 79-94
On the independence of P=NP, discrete case