wiki_research

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

crpq_minimization_problem (666B)

      1 # CRPQ minimization problem
      2 
      3 [Decision_problem] defined in [morvan2025homomorphism], p91:
      4 - Input: a [CRPQ] Q and integer k
      5 - Output: is there a [query_equivalent] [CRPQ] with at most k [atoms] which is equivalent to Q
      6 
      7 The problem is [EXPSPACE_hard] ([morvan2025homomorphism], Theorem IV.5.2) and in [2EXPSPACE] ([CRPQ_minimization_upper_bound], [morvan2025homomorphism], Theorem IV.3.1)
      8 
      9 In fact, by [morvan2025homomorphism] Theorem IV.5.2, it is already [EXPSPACE_hard] to determine if a [Boolean_CRPQ] with 4 variables is equivalent to a [Boolean_CRPQ] with a single atom
     10 
     11 See also: [ucrpq_minimization_problem]
     12 
     13 Up: [computational_problem], [CRPQ_minimization]