wiki_research

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

ucrpq_minimization_problem (797B)

      1 # UCRPQ minimization problem
      2 
      3 [Decision_problem] defined in [morvan2025homomorphism], p91:
      4 - Input: a [UCRPQ] Q and integer k
      5 - Output: is there a [query_equivalent] [UCRPQ] with at most k [atoms] which is equivalent to Q
      6 
      7 For [CRPQs], the problem is [EXPSPACE_hard] ([morvan2025homomorphism], Theorem IV.5.2) and in [2EXPSPACE] ([CRPQ_minimization_upper_bound], [morvan2025homomorphism], Theorem IV.3.1)
      8 
      9 For [UCRPQs], the problem is [EXPSPACE_complete] ([morvan2025homomorphism], Corollary IV.4.7)
     10 
     11 Different from [CRPQ_minimization] in the sense that there are [minimal_CRPQs] that admit a [query_equivalent] [UCRPQ] whose constituent [CRPQs] have fewer [atoms], cf [morvan2025homomorphism] Proposition IV.4.1
     12 
     13 Up: [crpq_minimization], [decision_problem]
     14 
     15 See also: [CRPQ_minimization_problem]