Parallella fasta-parameterdragbarhet studier hur parameteriserade problem kan lösas parallellt. Ett förvånansvärt stort antal parameteriserade problem medger en hög nivå av parallellisering, men detta betyder inte att vi också effektivt kan beräkna små problemkärnor parallellt: kända kärnalgoritmer är typiskt mycket sekventiella. I det här dokumentet fastställer vi ett antal övre och nedre gränser för kärnornas storlek som kan beräknas parallellt. Ett intressant fynd är att det finns komplexa avvägningar mellan kärnans storlek och djupet av de kretsar som behövs för att beräkna dem: För vertex-omslaget problem, kan en exponentiell kärna beräknas av AC 0 -kretsar, en kvadratisk kärna av TC 0 -kretsar, och en linjär kärna genom randomiserade NC-kretsar med derandomisering är möjligt endast om det är möjligt för det matchande problemet. Andra naturliga problem för vilka liknande (men kvantitativt olika) effekter kan observeras inkluderar träd sönderdelning problem parameteriserade av vertex täcknummer, den oriktade feedback vertex set problem, matchande problem, eller punkt linje täcka problem. Vi presenterar också naturliga problem för vilka datorkärnor i sig är sekventiella.
När det gäller parallella kärnalgoritmer är det känt att för många naturliga problem ju snabbare vi försöker beräkna en kärna parallellt, desto större kommer denna kärna att vara REF.
Computing Kernels in Parallel: Lower and Upper Bounds
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}