272 KB18 KB200820252016Raggi, Miguelštevilka:1letnik:10str. 1-8COBISSID:17732185ISSN:1855-3966URN:URN:NBN:SI:doc-B05X77KZenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneaAnstee-Sali conjectureAnstee-Sali domnevaforbidden configurationhipergrafhypergraphNP-completeNP-hardNP-polnNP-težekprepovedana konfiguracijasledtraceForbidden configurations| finding the number predicted by the Anstee-Sali conjecture is NP-hard|Let ?$F$? be a (possibly non-simple) hypergraph and let ?$\text{forb}(m, F)$? denote the maximum number of edges a simple hypergraph with ?$m$? vertices can have if it doesn't contain ?$F$? as a subhypergraph. A conjecture of Anstee and Sali predicts the asymptotic behaviour of ?$\text{forb}(m, F)$? for fixed ?$F$?. In this paper we prove that even finding this predicted asymptotic behaviour is an NP-hard problem, meaning that if the Anstee-Sali conjecture were true, finding the asymptotics of ?$\text{forb}(m, F)$? would be NP-hardNaj bo ?$F$? (ne nujno enostaven) hipergraf in naj ?$\text{forb}(m, F)$? označuje maksimalno število neusmerjenih povezav, ki jih lahko ima enostaven hipergraf z ?$m$? vozlišči, če ne vsebuje ?$F$? kot podhipergraf. Domneva, ki sta jo postavila Anstee in Sali, napoveduje asimptotsko vedenje ?$\text{forb}(m, F)$? za fiksen ?$F$?. V tem članku dokažemo, da je celo iskanje tega napovedanega asimptotskega vedenja NP-težek problem. To pomeni: če je Anstee-Sali domneva resnična, potem je iskanje asimptotočnega vedenja ?$\text{forb}(m, F)$? NP-težkoTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije