Name
Abstract | ||
|---|---|---|
We further develop the Fusion Method by exploringits similarities with the Ultraproduct Constructionin Model Theory. We use this analogy to re-prove aresult of Sipser regarding countable circuits, in a simplerway. In the finite case this analogy allows us togive a new characterization of co-NP in terms of theCLIQUE function. This gives a natural interpretationto the NP-completeness of the CLIQUE function.IntroductionIn this paper we further develop the analogy betweenRazborov's... |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1109/SCT.1994.315813 | Structure in Complexity Theory Conference |
Keywords | Field | DocType |
computational complexity,filtering and prediction theory,modelling,networks (circuits),switching functions,CLIQUE function,NP-completeness,co-NP,countable circuits,fusion method,model theory,ultrafilters,ultraproduct construction | Ultraproduct,Discrete mathematics,Combinatorics,Countable set,Clique,Analogy,Model theory,Mathematics,Computational complexity theory | Conference |
ISSN | ISBN | Citations |
1063-6870 | 0-8186-5670-0 | 2 |
PageRank | References | Authors |
0.48 | 7 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shai Ben-David | 1 | 2584 | 351.84 |
| Mauricio Karchmer | 2 | 571 | 54.29 |
| Eyal Kushilevitz | 3 | 2 | 0.48 |