Abstrakt. Kernelization är en stark och allmänt tillämpad teknik i utformningen av fasta-parameter algoritmer. I ett nötskal är en kärnalgoritm en polynom-tid transformation som omvandlar varje given parameteriserad instans till en likvärdig instans av samma problem, med storlek och parameter avgränsad av en funktion av parametern i inmatningen. En kärnalgoritm kallas en polynomkärna om storleken och parametern för utdatan är polynomiskt bundna av indataparametern. I detta dokument ger vi bevis för att ett brett spektrum av FPT-problem inte har polynomkärnor. Våra bevis bygger på hypoteser gjorda i den klassiska världen (d.v.s. P vs NP), och utvecklas runt en ny typ av algoritm för klassiska beslutsproblem, kallas en destillationsalgoritm, som kan vara av oberoende intresse. Med hjälp av begreppet destillationsalgoritmer utvecklar vi en generisk lågbunden motor som gör att vi kan visa att en mängd olika FPT-problem, som uppfyller vissa kriterier, inte kan ha polynomkärnor om inte polynomhierarkin kollapsar. Dessa inkluderar viktiga FPT-problem såsom k-Path, k-Minor Order Test, k-Planar Graph Subgraph Test, och flera andra. Vi visar också att en polynomkärna för parameteriserade problem som uppfyller något olika kriterier innebär en destillationsalgoritm för alla coNP-kompletta problem. Exempel på sådana problem är kPathwidth, k-Treewidth och k-Cutwidth. Dessutom tillåter vårt ramverk oss också att etablera coreization lägre gränser för optimeringsproblem (t.ex. Minsta dominerande uppsättning) parameteriserad av trädbredd, klickbredd, max. Grad, och så vidare. I den sista delen av tidningen studerar vi subexponentiella kärnalgoritmer, och undersöker dessa typer av kärnor ur en mer strukturell synvinkel. Våra resultat är de första negativa resultaten när det gäller polynomkärnor för naturliga FPT-problem. Bortsett från dessa, var de enda tidigare kända tekniker för att visa lägre gränser begränsade till linjära lägre gränser. Vi tror att våra resultat ger en glimt av vad som gör polynomisk kärnorisering i sig svårt i vissa typer av problem, och erbjuder också en tillgänglig plattform för att visa liknande resultat.
Mycket nyligen, Fellows et al. REF föreslår en ny metod som gör att vi kan visa att många problem inte har polynomstorlekskärnor under rimliga komplexa-teoretiska antaganden.
On problems without polynomial kernels
{'venue': 'Lect. Notes Comput. Sci', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}