Skip to main content

poly_kernel_lower_bound_ty

oxilean_std::parameterized_complexity::functions

Function poly_kernel_lower_bound_ty 

Source 
pub fn poly_kernel_lower_bound_ty() -> Expr
Expand description

PolynomialKernelLowerBound : ParameterizedProblem → Nat → Prop No polynomial kernel of size < k^c unless NP ⊆ coNP/poly.