"We give some conditional unprovability results about statements from structural complexity theory in weak arithmetic. In particular we show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S^1_2 exists in which NP is not in the second level of the linear hierarchy; and that a model of S^1_2 exists in which the polynomial hierarchy collapses to the linear hierarchy and in which the strict version of PH does not collapse to a finite level."@en . . "2" . "2"^^ . "1"^^ . "We give some conditional unprovability results about statements from structural complexity theory in weak arithmetic. In particular we show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of S^1_2 exists in which NP is not in the second level of the linear hierarchy; and that a model of S^1_2 exists in which the polynomial hierarchy collapses to the linear hierarchy and in which the strict version of PH does not collapse to a finite level." . . "Thapen, Neil" . . "[7B12CBE9FDC1]" . . "P(LC505), Z(AV0Z10190503)" . "387445" . "Kolodziejczyk, L.. A." . . "Polynomi\u00E1ln\u00ED a line\u00E1rn\u00ED hierarchie v modelech, kde neplat\u00ED slab\u00FD princip PHP"@cs . . "The polynomial and linear hierarchies in models where the weak pigeonhole principle fails"@en . "0022-4812" . "Polynomi\u00E1ln\u00ED a line\u00E1rn\u00ED hierarchie v modelech, kde neplat\u00ED slab\u00FD princip PHP"@cs . "Journal of Symbolic Logic" . . . "73" . "RIV/67985840:_____/08:00319585!RIV09-AV0-67985840" . "The polynomial and linear hierarchies in models where the weak pigeonhole principle fails" . . "The polynomial and linear hierarchies in models where the weak pigeonhole principle fails" . "Dok\u00E1zali jsme n\u011Bkolik podm\u00EDn\u011Bn\u00FDch v\u00FDsledk\u016F o nedokazatelnosti v\u011Bt ze struktur\u00E1ln\u00ED teorie slo\u017Eitosti a slab\u00E9 aritmetiky. Konkr\u00E9tn\u011B jsme uk\u00E1zali za p\u0159edpokladu, \u017Ee rozklad \u010D\u00EDsel je t\u011B\u017Ek\u00E1 operace, \u017Ee existuje model PV, ve kter\u00E9m polynomi\u00E1ln\u00ED hierarchie nekolapsuje na line\u00E1rn\u00ED hierarchii, \u017Ee existuje model S^1_2, ve kter\u00E9m NP nen\u00ED druh\u00E1 hladina line\u00E1rn\u00ED hierarchie a \u017Ee existuje model S^1_2, ve kter\u00E9m polynomi\u00E1ln\u00ED hierarchie kolapsuje na line\u00E1rn\u00ED hierarchii."@cs . . . "polynomial and linear hierarchies in models"@en . . . "RIV/67985840:_____/08:00319585" . . . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "The polynomial and linear hierarchies in models where the weak pigeonhole principle fails"@en . "000256103700013" . "15"^^ .