wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

query_evaluation_conjunctive_query (335B)

      1 # Conjunctive query evaluation
      2 
      3 CQ evaluation is [NP_complete] in [combined_complexity] and even in [query_complexity], cf [chandra1977optimal]
      4 
      5 dual: [constraint_satisfaction_problem], cf [other_side]
      6 
      7 Up: [query_evaluation], [conjunctive_query]
      8 
      9 See also: [Homomorphism_problem]
     10 
     11 Aliases: CQ evaluation, conjunctive query evaluation