Documentation
Complexitylib
.
Metacomplexity
.
MCSP
.
Succinct
.
NP
.
Internal
Search
return to top
source
Imports
Init
Complexitylib.Metacomplexity.MCSP.Succinct.NP.Defs
Complexitylib.Metacomplexity.MCSP.Succinct.Normalization.Internal
Complexitylib.Metacomplexity.MCSP.Succinct.Witness.Internal
Imported by
Complexity
.
SuccinctMCSP
.
verifyRawWitness_eq_true_iff_internal
Complexity
.
SuccinctMCSP
.
rawWitnessRelation_mem_FNP_of_pairLang_mem_P_internal
Complexity
.
SuccinctMCSP
.
mem_NP_of_pairLang_mem_P_internal
SuccinctMCSP witness-class packaging -- proof internals
#
source
theorem
Complexity
.
SuccinctMCSP
.
verifyRawWitness_eq_true_iff_internal
(
bits
witness
:
List
Bool
)
:
verifyRawWitness
bits
witness
=
true
↔
RawWitnessRelation
bits
witness
source
theorem
Complexity
.
SuccinctMCSP
.
rawWitnessRelation_mem_FNP_of_pairLang_mem_P_internal
(
hverifier
:
pairLang
RawWitnessRelation
∈
P
)
:
RawWitnessRelation
∈
FNP
source
theorem
Complexity
.
SuccinctMCSP
.
mem_NP_of_pairLang_mem_P_internal
(
hwitness
:
NP.WitnessNTMConstruction
)
(
hverifier
:
pairLang
RawWitnessRelation
∈
P
)
:
SuccinctMCSP
∈
NP