<p>How can a DAG-like resolution proof be transformed to a tree-like resolution proof?</p>

<p>Is such a transformation possible in polynomial time?</p>

CC BY-SA 4.0
2018-08-11T18:51:32.203Z
It's an exercise to come up with a transformation with exponential blow up, and that's sometimes necessary: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BIW03/biw03.pdf. Moreover, the paper shows a more efficient transformation than the trivial one.
Sasho Nikolov
CC BY-SA 4.0
2018-08-11T20:54:21.693Z
Thanks. the paper is a bit long. I'll read it carefully to see how the authors proceed.
RTK
<sat><proof-complexity>
Transforming a DAG-like resolution proof to a tree like resolution proof
RTK
# Transforming a DAG-like resolution proof to a tree like resolution proof

(Asked by: username_0 on 2018-08-11)

How can a DAG-like resolution proof be transformed to a tree-like resolution proof?

Is such a transformation possible in polynomial time?

**Tags:** sat, proof-complexity
> **Comments:**
> **username_1**: It's an exercise to come up with a transformation with exponential blow up, and that's sometimes necessary: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/BIW03/biw03.pdf. Moreover, the paper shows a more efficient transformation than the trivial one.  
> **username_0**: Thanks. the paper is a bit long. I'll read it carefully to see how the authors proceed.  

---

## 0 answers

