k-SAT

k-SAT restricts the boolean formula to CNF with (at most) k literals per clause

Parameters

  • nn: number of variables
  • kk: max number of literals per clause
  • cc: dependant on kk

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 1 of 1 algorithms

See more
Paturi, Pudlák, Saks, Zane (PPSZ) 20052005O∗(2n−cn/k)O^*(2^{n-cn/k})O(kn)

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table