LAC
/
Questionnaire-2024
3
0
Fork 0
Code Issues Pull Requests Projects Releases 12 Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
33 Commits
1 Branch
12 Tags
1.2 MiB
Tree: release_pr
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'release_pr'
${ noResults }
Questionnaire-2024/equivalence_checking/0005_sol.tex

3 lines
358 B
Raw Permalink Normal View History

added eqchecking chapter
2 months ago
​
​
  1. Given an original formula $\varphi$.
  2. The equisatisfiable formula in CNF after Tseitin encoding -- $CNF(\varphi)$ -- is \emph{linear} in the size of $\varphi$, since the number of variables and clauses introduced by Tseitin encoding is \emph{linear} in the size of $\varphi$.
  3. Using a truth table could result in an exponential blowup when constructing a CNF.