Catalog

Note:

Search your articles by the first title's letter

Know More

Ini adalah Website Artikel Universitas Kristen Petra   Anda dapat mencari artikel yang diinginkan dengan website ini.

Login                  Sign Up

Username Password
.
 

Welcome to our site

Kata sambutan

Article

Download Article

title:Proof Complexity In Algebraic Systems And Bounded Depth Frege Systems With Modular Counting
author:S. Buss
R. Impagliazzo
J. Krajícek
P. Pudlák
A. A. Razborov
J. Sgall
description:We prove a lower bound of the form N on the degree of polynomials in a Nullstellensatz refutation of the Count q polynomials over Zm , where q is a prime not dividing m. In addition, we give an explicit construction of a degree N design for the Count q principle over Zm . As a corollary, using Beame et al. (1994) we obtain a lower bound of the form 2 for the number of formulas in a constant-depth Frege proof of the modular counting principle Count q from instances of the counting principle Count m . We discuss
date:2010-05-07
2007-11-21
identifier:http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.5152
source:http://euclid.ucsd.edu/~sbuss/ResearchWeb/nullstellensatz/token.ps
relation:

10.1.1.109.380

10.1.1.100.8571

10.1.1.27.9017

10.1.1.42.2402

10.1.1.30.9530

10.1.1.55.5784

10.1.1.45.2040

10.1.1.103.2027

10.1.1.145.6065

10.1.1.50.50

10.1.1.19.2441

10.1.1.46.9613

10.1.1.16.2995

10.1.1.55.9956

10.1.1.51.4572

10.1.1.36.9973

10.1.1.27.5367

10.1.1.2.5515

10.1.1.46.9960

10.1.1.42.7041

10.1.1.3.6020

10.1.1.84.1481

10.1.1.93.2547

10.1.1.36.5560

10.1.1.94.480

10.1.1.11.3233

10.1.1.56.3160

10.1.1.38.9464

10.1.1.101.9657

10.1.1.66.8295

10.1.1.69.2922

10.1.1.71.5855

10.1.1.74.345

10.1.1.78.5725

10.1.1.123.4547

10.1.1.97.8370

10.1.1.110.7339

10.1.1.118.1242

10.1.1.124.3938

10.1.1.46.9995

10.1.1.11.3436

10.1.1.137.5051

10.1.1.149.9634

10.1.1.150.9282

10.1.1.158.4636

10.1.1.158.8850

sender : administrator
status : approved
.
.

Latest Releases & News


Says Who? -- Incorporating Source Credibility Issues into . . .
Frances L. Johnson
Stuart C. Shapiro


Proof Complexity In Algebraic Systems And Bounded Depth Frege Systems With Modular Counting
S. Buss
R. Impagliazzo
J. Krajícek
P. Pudlák
A. A. Razborov
J. Sgall


NetPDL: An Extensible XML-Based Language for Packet Header Description
Fulvio Risso
Mario Baldi


Extremal Problems for Colored Trees and Davenport-Schinzel Sequences
Martin Klazar


Automatic Image Captioning
Jia-Yu Pan
Hyung-Jeong Yang
Pinar Duygulu
Christos Faloutsos


The Guarded Fragment: Ins and Outs
Carlos Areces
Christof Monz
Hans de Nivelle
Maarten de Rijke

.