Search type Search syntax
Tags [tag]
Exact "words here"
Author user:1234
user:me (yours)
Score score:3 (3+)
score:0 (none)
Answers answers:3 (3+)
answers:0 (none)
isaccepted:yes
hasaccepted:no
inquestion:1234
Views views:250
Sections title:apples
body:"apples oranges"
URL url:"*.example.com"
Favorites infavorites:mine
infavorites:1234
Status closed:yes
duplicate:no
migrated:no
wiki:no
Types is:question
is:answer
Exclude -[tag]
-apples
For more details on advanced search visit our help page
Results tagged with Search options user 114

Questions related to the (computational) complexity of solving problems

6
votes
The proof is not correct. As you've indicated the reduction needs to go in the other direction, i.e. integer programming must be reduced to their problem, not the other way around.
answered Jan 6 '14 by Kyle Jones
2
votes
The exponential blowup when converting circuits to conjunctive normal form is avoided by introducing new variables to represent the output of each sub-circuit plus a simple set of rules represent each …
answered Apr 21 '15 by Kyle Jones
14
votes
As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment. This is because all NP-c …
answered Aug 29 '14 by Kyle Jones
1
vote
Your problem is NP-complete by the modern presentation of Schaefer's dichotomy theorem. You can also prove its NP-completeness by direct reduction of SAT to your problem. If a CNF formula has $n$ va …
answered Sep 29 '18 by Kyle Jones
9
votes
From the point of view of someone who writes code for a living, having a good familiarity with NP-completeness is important for: 1. Recognizing when you're barking up the wrong tree NP-complete prob …
answered Jun 2 '15 by Kyle Jones
4
votes
Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length? No, because no one has proven that distribution of terms is the only way to convert CNF to …
answered May 14 '15 by Kyle Jones
7
votes
(1) is hard to answer unless you clarify what you mean by "versions of SAT problem." If we limit ourselves to the classes listed in Schaefer's "The Complexity of Satisfiability Problems", the only no …
answered Sep 9 '13 by Kyle Jones
4
votes
Yes. The quantifiers can be ignored for the sake of the test since a quantified Horn formula is syntactically identical to an unquantified one except for the quantifiers. That is, a quantified Horn …
answered Jun 28 '14 by Kyle Jones
1
vote
Your reasoning is correct. Your "sum-of-products" is more commonly known as disjunctive normal form (DNF). It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so …
answered Sep 27 '16 by Kyle Jones
2
votes
The reduction is straightforward, but what's likely tripping you up is that while 3CNF clauses seem to describe what's needed for a satisfying assignment, what they do more directly is describe what a …
answered Nov 26 '15 by Kyle Jones
1
vote
The intersection of two non-NP-hard languages can be NP-hard. Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT instan …
answered Aug 28 '15 by Kyle Jones
1
vote
Use a SAT solver that also allows you to express pseudo-Boolean constraints. Encoding the verification of the existence of the tiling of an NxN grid as a CNF formula is straightforward. Each grid po …
answered Apr 11 '14 by Kyle Jones
4
votes
Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable? The problem is provably NP-c …
answered Jul 23 '17 by Kyle Jones
11
votes
The deterministic time hierarchy theorem precludes all problems in P being decided in linear time. If you try to reduce a problem to HORN-SAT that requires more than linear time to decide, you'll fin …
answered Aug 4 '15 by Kyle Jones
4
votes
The trick to the reduction is to use numbers to encode statements about the 3CNF formula, crafting those numbers in such a way that you can later make an arithmetic proposition about the numbers that …
answered Apr 22 by Kyle Jones

15 30 50 per page