Skip to main content
Download PDF
- Main
Bounded-Depth Frege with Counting Principles Polynomially Simulates Nullstellensatz Refutations
Abstract
We show that bounded-depth Frege systems with counting principles modulo m can polynomially simulate Nullstellensatz refutations modulo m. This establishes new upper bounds for proofs of certain tautologies in bounded-depth Frege with counting axioms systems. When combined with another result of the authors, this simulation establishes a size (as opposed to a degree) separation between Nullstellensatz and polynomial calculus refutations.
Pre-2018 CSE ID: CS2001-0686
Main Content
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%