2-SAT reduction to Easy Puzzle Solving

Question

Introduction

I've been developing interest in complexity classes and thought I was unable to prove my problem is NP hard, so I wanted to see if it was P-hard. I wanted to see if my puzzle solving is special. I have linked a previous question of mine to help clarify what is mentioned below. Explained here

Random Instance of 2-SAT used for attempt reduction

I took an instance of my problem X

Let's say my problem X is determining if a puzzle is valid for my language

(a∨¬b)∧(¬a∨b)∧(¬a∨¬b)∧(a∨¬c)

Instance of X

a = shift(L) puzzle

¬ a = invalid puzzle

¬b = invalid puzzle

b = shift(L) puzzle

---

Reduction into Shorter Instance

(a∨¬b)∧(¬a∨b)

This boolean expression is only checking for 2-sat. Being True (valid puzzle) or False (invalid puzzle).

My idea is that a deterministic machine will consider n^2 x n^2 puzzles as invalid if the lower right-hand box is not filled. My puzzles are solved in quadratic time when provided a puzzle with this n x n box. Any other puzzle will simply fail to be solved if it does not follow my language. I have used an algorithm that can determine in poly-time that those failed puzzles are invalid puzzles. Because, the solver will not know it as an invalid puzzle. So it will try to map it out in my language thus giving an invalid puzzle.

Question

I have the algorithm and proven that it works in poly-time, the problem is that I only know how to prove it by showing the algorithm. I just don't know how to write it out mathematically. How would I properly do this?

Answer 1

I'm going to need to question your premise here.

I have no doubt that you can poly-time reduce 2SAT to your custom problem. But you can poly-time reduce 2SAT to pretty much anything. The idea of "P-hardness" under poly-time reduction isn't really a useful one.

For example, let's take the following problem:

IS-IT-ONE: given a single bit, is that bit a 1?

This problem is "P-hard" under poly-time reduction. For example, I can reduce 2SAT to it:

Reduction from 2SAT to IS-IT-ONE

• Solve 2SAT the usual way
• If the problem is satisfiable, let $B$ be 1
• If the problem is unsatisfiable, let $B$ be 0
• Run IS-IT-ONE on $B$ and return the result

This reduction runs in poly-time, because solving 2SAT can be done in poly-time.

In other words:

Every problem in P can be poly-time reduced to any other non-trivial problem.

(Only two languages are considered "trivial" for this purpose: "return true" and "return false", aka $\Sigma^*$ and $\varnothing$.)

If you're interested in classes smaller than P, great! There are several of them, such as L: the set of problems that can be solved using a logarithmic amount of memory. It may or may not be the same as P—that's an open problem.

But if you want to talk about P versus L or NL or anything else within P, you can't use poly-time reductions any more. When talking about L, for example, you'll usually want a log-space reduction, using a Turing machine with writable tape bounded by the log of the input size. These aren't as famous as poly-time reductions, but they're still quite important in complexity theory.