EXTENDED NULLSTELLENSATZ PROOF SYSTEMS

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10487988" target="_blank" >RIV/00216208:11320/24:10487988 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=xbOt~UqDIx" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=xbOt~UqDIx</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1090/proc/16709" target="_blank" >10.1090/proc/16709</a>

Jazyk výsledku

angličtina

Název v původním jazyce

EXTENDED NULLSTELLENSATZ PROOF SYSTEMS

Popis výsledku v původním jazyce

For a finite set F of polynomials from F-p[(x) over bar] (p is a fixed prime) containing all polynomials x(2)-x, a Nullstellensatz proof of the unsolvability of the systemf =0, all f is an element of Fin F-p is an F-p[(x) over bar]-linear combination Sigma(f is an element of F) h(f)center dot f that equals to 1 in F-p[(x) over bar]. The measure of complexity of such a proof is its degree: max(f) deg(h(f)f).We study the problem to establish degree lower bounds for some extended NS proof systems: these systems prove the unsolvability of F (in F-p) by proving the unsolvability of a bigger set F boolean OR E, where the set E subset of F-p[(x) over bar, (r) over bar] contains all polynomials r(p)-r and satisfies the following soundness condition:center dot Any 0,1-assignment (a) over bar to variables &lt;(x)over bar can be appended by an Fp-assignment &lt;(b)over bar&gt; to variables (r) over bar such that for all g is an element of E it holds that g((a) over bar, (b) over bar)=0.We define a notion of pseudo-solutions of F and prove that the existence of pseudo-solutions with suitable parameters implies lower bounds for two extended NS proof systems ENS and UENS defined by Buss et al [Comput. Complexity 6 (1996/97), pp. 256-298]. Further we give a combinatorial example of F and candidate pseudo-solutions based on the pigeonhole principle.

Název v anglickém jazyce

EXTENDED NULLSTELLENSATZ PROOF SYSTEMS

Popis výsledku anglicky

For a finite set F of polynomials from F-p[(x) over bar] (p is a fixed prime) containing all polynomials x(2)-x, a Nullstellensatz proof of the unsolvability of the systemf =0, all f is an element of Fin F-p is an F-p[(x) over bar]-linear combination Sigma(f is an element of F) h(f)center dot f that equals to 1 in F-p[(x) over bar]. The measure of complexity of such a proof is its degree: max(f) deg(h(f)f).We study the problem to establish degree lower bounds for some extended NS proof systems: these systems prove the unsolvability of F (in F-p) by proving the unsolvability of a bigger set F boolean OR E, where the set E subset of F-p[(x) over bar, (r) over bar] contains all polynomials r(p)-r and satisfies the following soundness condition:center dot Any 0,1-assignment (a) over bar to variables &lt;(x)over bar can be appended by an Fp-assignment &lt;(b)over bar&gt; to variables (r) over bar such that for all g is an element of E it holds that g((a) over bar, (b) over bar)=0.We define a notion of pseudo-solutions of F and prove that the existence of pseudo-solutions with suitable parameters implies lower bounds for two extended NS proof systems ENS and UENS defined by Buss et al [Comput. Complexity 6 (1996/97), pp. 256-298]. Further we give a combinatorial example of F and candidate pseudo-solutions based on the pigeonhole principle.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Proceedings of the American Mathematical Society

ISSN

0002-9939

e-ISSN

1088-6826

Svazek periodika

152,

Číslo periodika v rámci svazku

11

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

12

Strana od-do

4881-4892

Kód UT WoS článku

001327026300001

EID výsledku v databázi Scopus

2-s2.0-85205826145