mul = { 1 => {1 => 1, :i => :i, :j => :j, :k => :k, -1 => -1, :I => :I, :J => :J, :K => :K},
:i => {1 => :i, :i => -1, :j => :k, :k => :J, -1 => :I, :I => 1, :J => :K, :K => :j},
:j => {1 => :j, :i => :K, :j => -1, :k => :i, -1 => :J, :I => :k, :J => 1, :K => :I},
:k => {1 => :k, :i => :j, :j => :I, :k => -1, -1 => :K, :I => :J, :J => :i, :K => 1},
-1 => {1 => -1, :i => :I, :j => :J, :k => :K, -1 => 1, :I => :i, :J => :j, :K => :k},
:I => {1 => :I, :i => 1, :j => :K, :k => :j, -1 => :i, :I => -1, :J => :k, :K => :J},
To my knowledge there doesn't exist a $O(n)$ worst-case algorithm that solves the following problem:
Given a sequence of integers of length $n$, find the permutation where every element is less than or equal to its successor.
But is there a proof that it doesn't exist?
Note that I'm not ...
What are the best current lower bounds for time and circuit depth for 3SAT?
