EXTENDED NULLSTELLENSATZ PROOF SYSTEMS

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
EXTENDED NULLSTELLENSATZ PROOF SYSTEMS
Original language description
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 <(x)over bar can be appended by an Fp-assignment <(b)over bar> 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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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

Similar results(10)