Skip to main content
edited tags
Link
Kaveh
  • 22.5k
  • 4
  • 52
  • 112
Tweeted twitter.com/#!/StackCompSci/status/237926832765280257
unified tex, some language; edited title
Source Link
Juho
  • 22.8k
  • 7
  • 62
  • 117

How much can we reduce the number of clauses by converting from k$k$-SAT to $(k+m)$-SAT?

If we suppose that we start with an instance of k$k$-SAT, and try converting the problem to an instance of (k+m)$(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we garaunteeguarantee a reduction in the total amount of clauses?

I realized after posting that we can't gauranteeguarantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we garaunteeguarantee the total number of clauses can be reduced by? ForFor instance, if we start with k$k$-SAT with $n_k$ clauses, what is the smallest garaunteedguaranteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to (k+m)$(k+m)$-SAT?

More importantly, how do we carry out this conversion?

How much can we reduce number of clauses by converting from k-SAT to (k+m)-SAT?

If we suppose that we start with an instance of k-SAT, and try converting the problem to an instance of (k+m)-SAT, where there are $(k+m)$ literals per clause, can we garauntee a reduction in the total amount of clauses?

I realized after posting that we can't gaurantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we garauntee the total number of clauses can be reduced by? For instance, if we start with k-SAT with $n_k$ clauses, what is the smallest garaunteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to (k+m)-SAT?

More importantly, how do we carry out this conversion?

How much can we reduce the number of clauses by converting from $k$-SAT to $(k+m)$-SAT?

If we suppose that we start with an instance of $k$-SAT, and try converting the problem to an instance of $(k+m)$-SAT, where there are $(k+m)$ literals per clause, can we guarantee a reduction in the total amount of clauses?

I realized after posting that we can't guarantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we guarantee the total number of clauses can be reduced by? For instance, if we start with $k$-SAT with $n_k$ clauses, what is the smallest guaranteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to $(k+m)$-SAT?

More importantly, how do we carry out this conversion?

Deleted the "maybe this should migrate" portion of the question.
Source Link
Matt Groff
  • 892
  • 1
  • 7
  • 16

If we suppose that we start with an instance of k-SAT, and try converting the problem to an instance of (k+m)-SAT, where there are $(k+m)$ literals per clause, can we garauntee a reduction in the total amount of clauses?

I realized after posting that we can't gaurantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we garauntee the total number of clauses can be reduced by? For instance, if we start with k-SAT with $n_k$ clauses, what is the smallest garaunteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to (k+m)-SAT?

More importantly, how do we carry out this conversion?

MAYBE THIS SHOULD MIGRATE

I'm not sure if this is appropriate for Theoretical Computer Science as a research question, so I posted here first.

If we suppose that we start with an instance of k-SAT, and try converting the problem to an instance of (k+m)-SAT, where there are $(k+m)$ literals per clause, can we garauntee a reduction in the total amount of clauses?

I realized after posting that we can't gaurantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we garauntee the total number of clauses can be reduced by? For instance, if we start with k-SAT with $n_k$ clauses, what is the smallest garaunteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to (k+m)-SAT?

More importantly, how do we carry out this conversion?

MAYBE THIS SHOULD MIGRATE

I'm not sure if this is appropriate for Theoretical Computer Science as a research question, so I posted here first.

If we suppose that we start with an instance of k-SAT, and try converting the problem to an instance of (k+m)-SAT, where there are $(k+m)$ literals per clause, can we garauntee a reduction in the total amount of clauses?

I realized after posting that we can't gaurantee that the number of clauses can be reduced. However, I wonder if we have $n$ clauses, could we get something like $n/k + O(1)$ clauses by some "reduction" technique?

If so, how much can we garauntee the total number of clauses can be reduced by? For instance, if we start with k-SAT with $n_k$ clauses, what is the smallest garaunteed $n_{k+m}$, the new amount of clauses, that will result if we convert this instance to (k+m)-SAT?

More importantly, how do we carry out this conversion?

Added a new question about reducing clauses.
Source Link
Matt Groff
  • 892
  • 1
  • 7
  • 16
Loading
Source Link
Matt Groff
  • 892
  • 1
  • 7
  • 16
Loading