-1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Okay, I'll take a look into log space for a few days and try and see what I can get. I share this in form of question on CS. Preferably, on meta first. $\endgroup$ – Travis Wells May 16 at 19:47
  • 3
    $\begingroup$ @TravisWells I'd suggest taking some time away from your simplified-sudoku generator for a bit, too. Read up on complexity theory, and try some NP-hardness proofs for other problems. Then focus on log-space, and try some log-space reductions for other problems too, focusing on the difference between P and L. Then come back to your sudoku generator. $\endgroup$ – Draconis May 16 at 20:02
  • $\begingroup$ I agree that I need to take a break, I've already starting to understand how to reduce SAT into a 3-SAT Instance. I've managed to follow restricted reductions. 3-SAT to vertex cover is probably easier to understand. Given time, may we take this to chat so that I can learn this quickly as possible? I have a link to this. andrew.cmu.edu/user/ko/pdfs/lecture-21.pdf $\endgroup$ – Travis Wells May 16 at 23:02
  • 1
    $\begingroup$ @TravisWells pick a book, if you want to learn as quickly as possible, throw away your shifter-mapper, please. $\endgroup$ – Evil May 17 at 13:54
  • 1
    $\begingroup$ @TravisWells I agree with Evil, honestly. Your fixation on this shifter-mapper-thing is holding you back, especially since you can't even state what the problem is in a succinct way: your explanation is scattered across four different web pages now and involves sentences like "let shift by shift be defined by the formula x by y" which I can't make heads or tails of. I can tell you right now that your new question almost certainly isn't #P-complete, since #P is defined in terms of NP, and I'm confident your problem isn't NP-complete (though I don't understand it well enough to prove anything). $\endgroup$ – Draconis May 17 at 18:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.