wimmers poly-reductions issues

wimmers / poly-reductions

Polynomial-time reductions in Isabelle/HOL

2 stars 13 forks source link

issues

Newest

Newest Most commented Recently updated Oldest Least commented Least recently updated

refine reduction from `HOL` to `HOL-Nat`

#37 BilelGho opened 3 years ago
1
Memory bound for IMP-

#36 notiho closed 3 years ago
1
Fix some broken proof steps in Cook Levin

#35 notiho closed 3 years ago
0
Added final HOL version of the Cook-Levin thm

#34 mabdula closed 3 years ago
0
Proof of Cook-Levin at HOL level

#33 mabdula closed 3 years ago
1
Cleanup IMP- to SAS+ proofs

#32 mabdula opened 3 years ago
0
Prove Memory Bound for IMP-

#31 notiho opened 3 years ago
0
Pull request: add new operations for `IMP-`

#30 BilelGho closed 3 years ago
4
Create new arithmetical operations for `IMP-`

#29 BilelGho closed 3 years ago
0
Reduction from IMP- to IMP--

#28 notiho closed 3 years ago
1
Definitions of P, NP, polynomial time and space bounding, reductions

#27 BilelGho closed 3 years ago
1
Prove that SAT is NP

#26 BilelGho opened 3 years ago
1
IMP- to SAS+

#25 notiho closed 3 years ago
0
Reduction from IMP-- to SAS+

#24 notiho closed 3 years ago
1
Imp minus

#23 notiho closed 3 years ago
1
Cook-Levin Theorem

#22 maxhaslbeck opened 3 years ago
1
`IMP- to SAT`construction has polynomial blowup

#21 maxhaslbeck opened 3 years ago
0
`IMP- to SAT`on HOL level, functional correctness

#20 maxhaslbeck opened 3 years ago
1
Proof Sketch of Cook-Levin Theorem

#19 maxhaslbeck closed 3 years ago
1
Stating Cook-Levin

#18 maxhaslbeck closed 3 years ago
1
`IMP-` infrastructure

#17 maxhaslbeck opened 3 years ago
0
Translation from NREST- to IMP-

#16 wimmers opened 4 years ago
0
Translation from NREST to NREST-

#15 wimmers opened 4 years ago
0
Define NREST-

#14 wimmers opened 4 years ago
0
Define IMP-

#13 wimmers closed 3 years ago
2
Implement and refine the reduction from IMP- to SAT

#12 wimmers opened 4 years ago
0
Refine the reduction from SAT to 3-SAT

#11 wimmers opened 4 years ago
0
Show that reduction from SAS+ to SAT is polynomial time

#10 wimmers opened 4 years ago
0
Show that reduction from IMP- to SAS+ is polynomial time

#9 wimmers opened 4 years ago
0
Reduction from IMP- to SAS+

#8 wimmers opened 4 years ago
5
Decide whether LLVM IR is WHILET

#7 wimmers closed 4 years ago
1
Refinement of simple problems to IMP-

#6 wimmers opened 4 years ago
1
Reduction from SAT to 3-SAT

#5 wimmers opened 4 years ago
0
Finish the reduction from 3-SAT or SAT to 0-1 integer programming

#4 wimmers opened 4 years ago
0
Complete the subtree rooted under CHROMATIC NUMBERS in Karp's 21 problems

#3 wimmers opened 4 years ago
0
Refactor graph auxiliaries to use `Graph_Theory.Pair_Digraph`

#2 wimmers opened 4 years ago
1
Added some more reductions

#1 riedersa closed 4 years ago
0