Higher-Dimensional Potential Heuristics: Lower Bound Criterion and Connection to Correlation Complexity

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-05 17:45:48

Abstract: The correlation complexity is a measure of planning tasks indicating how hard they are. This measure is based on the question "What dimension is needed to express a heuristic as a potential heuristic?". In the introducing work, the authors provided sufficient criteria to detect a correlation complexity of at least 2 on a planning task. They also introduced an example of a planning task with correlation complexity 3. In this work, we introduce a criterion to detect a lower bound for the aforementioned question. This can also be used to detect an arbitrary correlation complexity and extend the mentioned example to show with the new criterion that planning tasks with arbitrary correlation complexity exist.

Main paper: 
 n states criterion: 
 We first state some definitions, notations, and lemma. Thereby we will introduce the Π ≤k construction to formulate the 2 n states criterion. The Π ≤k construction is similar to the P m construction (Haslum 2009) , to the Π C compilation (Steinmetz and Hoffmann 2018) , and to fluent merging (van den Briel, Kambhampati, and Vossen 2007). We discuss the similarities and differences in the related work section.The Π ≤k construction assumes an arbitrary order of the state variables. Definition 3 (Π ≤k construction). Let Π = ⟨V, I, O, γ⟩ a planning task. Let V be arbitrarily ordered,V = {v 1 , . . . , v |V | }. Let s be a state and k ≤ |V |. Let p ⊇ {⟨v i1 , d i1 ⟩, . . . , ⟨v i k , d i k ⟩} be a partial state with i a < i b for each 0 < a < b ≤ k. We call meta {i1,...,i k } (p) = ⟨v ⟨i1,...,i k ⟩ , ⟨d i1 , . . . , d i k ⟩⟩ a metafact with the metavariable v ⟨i1,...,i k ⟩ . The domain of the metavariable is k j=1 dom(v ij ).The size of the metafact/metavariable is k.We say metavariable v l is created from variable v t if t ∈ l, we refer to these variables with creators(v l ).With meta ≤k (s) = S⊆V,|S|≤k {meta S (s)} we denote the set of all metafacts from s of size up to k. We call meta ≤k (s) the metastate of size k of s and use the shorthand notation s ≤k and the set of its metavariables as V ≤k . The Π ≤k construction is the set {meta ≤k (s)|s ∈ Π}.Let us look at an example. In the Termes domain a robot has to build towers out of blocks on a 2D grid map. These blocks are also used to build stairs to reach the top of the towers. The robot can move to neighboring cells that contain a tower at most one level apart from the level the robot is at. It can change the height of a neighboring tower by placing/removing a block. A block can only be placed if the robot carries one and the neighboring tower is on the same level as the robot. Removing a block is only possible if the neighboring tower is one level above the robot and it is not carrying anything. Additionally, the robot can create/destroy blocks if it is at the deposit cell. It is not allowed to place blocks on this cell.Consider a task with 4 cells, one of them the deposit, and a maximal tower height of 3. The state variables (without the constants, ordered as written) isV = {v height2 , v height3 , v height4 , v robotAt , v robotHand }, with domain {0, 1, 2, 3} for v height2 , v height3 and v height4 , dom(v robotAt ) = {cell1, cell2, cell3, cell4},and dom(v r obotHand) = {f ree, f ull}. Let initial state beI ={v height2 → 1, v height3 → 1, v height4 → 3, v robotAt → cell2, v robotHand → f ree}.The corresponding metastate I V ≤2 contains 31 metafacts and is a superset of{v ⟨⟩ → ⟨⟩, v ⟨height2⟩ → ⟨1⟩, v ⟨robotHand⟩ → ⟨f ree⟩, v ⟨robotAt,robotHand⟩ → ⟨cell2, f ree⟩, v ⟨height2,height4⟩ → ⟨1, 3⟩}.We have facts in the metastate that encode multiple facts at once. With the metastates, we can artificially reduce the dimension of a potential heuristic.Definition 4 (k-synchronized heuristic). Let k ∈ N 0 , Π a planning task. A function h ′ : Π ≤k → R is a k- synchronized heuristic of the heuristic h on Π if h ′ (s ≤k ) = h(s) for each state s in Π.Lemma 1. Let Π = ⟨V, I, O, γ⟩ be a planning task. If there exists a potential heuristic h pot of dimension k on Π then there exists a k-synchronized potential heuristic h ′pot of dimension 1.Proof. We remember that h pot (s) = p∈P (w(p) • [p ⊆ s]).For each partial assignment p = {v i1 → d i1 , . . . , v im → d im } with |p| ≤ k and p ⊆ s there exists a corresponding metafact f p = (v ⟨i1,...,im⟩ → ⟨d i1 , . . . , d im ⟩) in the metastate s ≤k and therefore a partial assignment p * = {f p } of size 1. Let P * be the set of all possible partial assignments of size 1 in Π ≤k . By choosing w ′ (p * ) = w(p) for each p we see thath pot (s) = p∈P (w(p) • [p ⊆ s]) = p * ∈P * (w ′ (p * ) • [p * ⊆ s ≤k ]) = h ′pot (s ≤k ).Looking at the contrapositive of Lemma 1 we see that we can use the metastates of size k to check if it is impossible to represent a given heuristic as a potential heuristic of dimension k. We will use this to prove the 2 n states criterion.In the following, we always use the metastates to be projected. If a subset D ⊆ V ≤k is used for the mapping of a state s to a different set of metavariables D we mean with s D the metastate s ≤k projected to D, denoted as s D := (s ≤k ) D .Theorem 5 (2 n States Criterion). Let n ∈ N 1 , Π = ⟨V, I, O, γ⟩ be a planning task, h be a potential heuristic on Π. If there exist states s 0 , . . . , s 2 n -1 in Π and a partition{D 0 , . . . , D n-1 } of V ≤n-1 and j * ∈ [0, 2 n-1 -1] such that: h(s 2•j * ) > h(s 2•j * +1 ) h(s 2•j ) ≥ h(s 2•j+1 ) for all j ∈ [0, 2 n-1 -1] \ {j * } and ∀d ∈ [0, n -1]∀g ∈ [0,2 n-1-d -1]∀i ∈ [0, 2 d -1] : s D d g•2 d+1 +i = s D d (g+1)•2 d+1 -1-i (1)then the dimension of h is at least n. Before we prove the 2 n states criterion we want to shed light on the interpretation of condition (1). For a fixed d = 320 n -1 one can consider the states s 0 , . . . , s 2 n -1 split into 2 parts. The first part contains s 0 , . . . , s 2 n-1 -1 and the second part contains s 2 n-1 , . . . , s 2 n -1 . Variable g stays 0, only i iterates. The left-hand side of the equation iterates through the first part forwards and the right-hand side through the 325 second part backward.For d = n -2, one can consider the two parts split again in the middle resulting in 4 parts. With g = 0, the left-hand side of the equation iterates through the first part forward and the second part backward. For g = 1, the left-hand side 330 of the equation iterates through the third part forward and the fourth part backward.For decreasing d the number of such parts doubles and the left-hand side iterates through the odd parts forward and the right-hand side iterates through the even parts backwards. 335 Until d = 0, there we produce half as many parts as states. Variable i does not iterate, only g does. The left-hand side of the equation iterates through the states with even index and the right-hand side through the states with odd index. Table 1 shows the example values for n = 4. Looking 340 at the red indicated numbers we see that state s 6 has to be equal to: (i) s 9 under projection to D 3 , (ii) s 1 under projection to D 2 , (iii) s 5 under projection to D 1 , and (iv) s 7 under projection to D 0 .Proof. Assume there exists a potential heuristic h ′ of di-345 mension 1 on the task Π ≤n-1 , with h ′ being an n -1synchronized heuristic to h, and a partition {D 0 , . . . , D n-1 } of V ≤n-1 and j * ∈ [0, 2 n-1 -1] such that:h(s 2•j * ) > h(s 2•j * +1 ), h(s 2•j ) ≥ h(s 2•j+1 ) for all j ∈ [0, 2 n-1 -1] \ {j * } (2) and ∀d ∈ [0, n -1]∀g ∈ [0, 2 n-1-d -1]∀i ∈ [0, 2 d -1] : s D d g•2 d+1 +i = s D d (g+1)•2 d+1 -1-i 2 n-1 -1 j=0 h(s 2•j ) > 2 n-1 -1 j=0 h(s 2•j+1 )We see that the left-hand side only contains states with an even index and the right-hand side contains only states with an odd index. With h ′ being of dimension 1 and n -1synchronized to h we can split h(st ) = n-1 d=0 h ′ (s D d t ) - n-2 d=0 w(∅) and obtain 355 2 n-1 -1 j=0 n-1 d=0 h ′ (s D d 2•j ) > 2 n-1 -1 j=0 n-1 d=0 h ′ (s D d 2•j+1 ) (3) Consider s D d g•2 d+1 +i = s D d (g+1)•2 d+1 -1-ifor an arbitrary d. The index on the left-hand side is even iff i is even. The index on the right-hand side is odd iff i is even.We conclude that for every fixed d and for every odd x with x ∈ [0, 2 n -1] there exists one even y with y 4) we can iterate through all d with d ∈ [0, n -1] and all even numbers p with p ∈ [0, 2 n -1]. We find a corresponding odd q with q ∈ [0, 2 n -1] such that s D d p = s D d q and reduce (3) by removing h ′ (s D d p ) on the left-365 hand side and h ′ (s D d q ) on the right-hand side. This change does not affect the inequality. However, all summands are removed and we get the inequality 0 > 0 which is a contradiction.∈ [0, 2 n - 1] such that s D d x = s D d y (4) With equation (We conclude that there exists no n -1-synchronized potential heuristic to h of dimension 1. With the contrapositive of Lemma 1, we conclude that no potential heuristic h on Π with dimension n -1 exists. Therefore, the dimension of h is at least n.The 2 2 states criterion is equivalent to the quadruple cri-375 terion with the minor detail that {D 0 , D 1 } is a partition of V ≤1 , unlike {W, M }, which is a partition of V . The difference is minor as V ≤1 only contains meta variables of size 1 and v ⟨⟩ , which is constant.The 2 1 states criterion projects the 2 states to the set {v ⟨⟩ }.There, all states are the same, trivially. What remains is the condition that there are 2 states with different heuristic values. Theorem 6. Let n ∈ N 1 , Π = ⟨V, I, O, γ⟩ be a planning task. If for each potential heuristic h pot that is DDA on Π there exist states s 0 , . . . , sEQUATION∀d ∈ [0, n -1]∀g ∈ [0,2 n-1-d -1]∀i ∈ [0, 2 d -1] : s D d g•2 d+1 +i = s D d (g+1)•2 d+1 -1-ithen the correlation complexity of Π is at least n.Note that these states and the partition do not have to be the same for all DDA potential heuristics.Proof. We know that the correlation complexity of a task Π is the minimal dimension over all potential heuristics that are DDA on Π. The condition of Theorem 6 implies that any DDA potential heuristic fulfills the condition for the 2 n states criterion. Therefore, we conclude that each potential heuristic that is DDA on Π is of dimension at least n. Therefore, the correlation complexity of Π is at least n.With the shifted view from operators to states we were able to construct a family of criterions to detect arbitrary correlation complexity. Now we want to shift the view back to operators and macros as they are in some sense more accessible for higher-level arguments. We create a generalization of the criterion from Theorem 1. Definition 5 (Macro Folding). The macros -→ m, ←m are nmatching if we can decompose both into n base macros, where the i-th base macro of -→ m is the inverse of the n-i+1-th base macro of ← - m for each i ∈ [1, n].We say a macro m is folded one time on crease↷ m 1 if we can decompose it into 3 macros [ - → m 0 , ↷ m 1 , ← - m 0 ] with - → m 0 1-matching ← - m 0 .Here we call ↷ m 1 the first crease and -→ m 0 the 0-th crease. We say a macro m is Note that if a macro m is folded n times it is also folded k times for all 0 ≤ k ≤ n. Asking for the k-th creases is therefore ill-defined, without specifying how many total creases are considered. In the following, we implicitly mean the largest possible value we established for the considered macro.folded n > 1 times if it is folded once on crease ↷ m n (the n-th crease of m) and we can decompose it into 7 macros [ - → m n-1 , ↷ m n-1 , ← - m n-1 , ↷ m n , - → m ′ n-1 , ↶ m n-1 , ← - m ′ n-1 ] where [ - → m n-1 , ↷ m n-1 , ← - m n-1 ] and [ - → m ′ n-1 , ↶ m n-1 , ← - m ′ n-1 ] are 2 n -1-matching,An intuitive interpretation of a folded macro [ -→ m, ↷ m, ←m] is to view -→ m as the set-up and ←m as the tear-down. The crease ↷ m is the actually desired action. If the macro is folded multiple times there are recursive occurrences of this set-up and tear-down behavior.The Termes task described earlier with goal {v height2 → 1, v height3 → 1, v height4 → 2, } is an example for that. The task is to remove the 3rd block from cell 4 (and keep the other towers the same). Note that the encoding does not distinguish the individual blocks.The set-up for that is to carry a block to cell 2. From there the robot can place that block on cell 3, climb on it, pick up the block from cell 4, and carry it to cell 2. We view this macro of 4 operators as the crease. Afterward, the tear-down is to get rid of the auxiliary block.To execute the set-up a secondary set-up is needed. The robot has to move to the deposit first (secondary set-up), create a block (crease of the primary set-up), and move back up with it (secondary tear-down).Similarly, for the tear-down. A secondary set-up is needed there, as well. The robot has to carry the block it holds to the deposit (secondary set-up), destroy the block (crease of the primary tear-down), and move back up (secondary teardown).The robot is required to come back to cell 2 after destroying the carried block, to pick up the auxiliary block. The described order of operators is the only one solving the task (without cycles or transitions after reaching the goal). Therefore, the macro of the primary set-up and primary tear-down are critical.We provided this task in PDDL in Appendix B together with the plan and a visualization of the folded macro.Lemma 2 (Orthogonality Lemma). For any state s and applicable,1 time folded macro m = [ - → m n , . . . , - → m 0 , ↷ m, ← - m 0 , . . . , ← - m n ] with crease ↷ m it holds for all i ∈ [0, n]: • s - → m i ! ↷ m! = s ↷ m! - → m i ! , • vars(eff( - → m i )) ∩ vars(eff( ↷ m)) = ∅, and • s m = s ↷ m! . Proof. Case (i) i = 0: Assume s - → m i ! ↷ m! ̸ = s ↷ m! - → m i ! , therefore there is a v ∈ vars(eff( - → m i )) ∩ vars(eff( ↷ m)), and v → d A is an effect of - → m i and v → d B is an effect of ↷ m.We know d A ̸ = d B , due to our assumption. Then ← -m i is not applicable in state s - → m i ↷ mas it has v → d A as precondition, because it is in normal form and inverse to -→ m i . This provides a contradiction to m being an applicable macro.This also provides us that s -→ m 0 ! ↷ m! ← - m 0 ! = s ↷ m! . Case (ii) i > 0: Consider the macro [ - → m i-1 , . . . , - → m 0 , ↷ m, ← - m 0 , . . . , ← - m i-1] as the crease of m and relabel the indices to match case (i). EQUATIONs n+i := s n+i-1 ← - m i with ← - m i being the i-th base macro of ← - m for i ∈ [1, n -1]. Then for all j ∈ [0, n -1] s n-1-j ↷ m! = s n+j . Proof. Let j ∈ [0, n -1]. Since m is folded on crease ↷ m we conclude with Lemma 2 that s n-1-j ↷ m! = s n-1-j [ - → m n-j+1 , . . . , - → m n , ↷ m, ← - m n . . . ← - m n-j+1 ] = s n+j by construction.With that, we introduce the new criterion.Theorem 7 (Folded Macro Criterion). Let Π be a planning task in normal form, and let -→ m and ←m be critical macros of Π that are 2 n -1-matching and folded n -1 times, then Π has correlation complexity of at least n + 1.Proof. Since - → m and ← - m are critical each plan for Π is of the form [m I , - → m, ↷ m, ← - m, m γ ] (or - → m, ← -m swapped but without loss of generality we assume the former; m I and/or m γ 500 might be empty) and therefore contains the macro m :=[ - → m, ↷ m, ← - m].This macro is folded n times, with the n-th crease at ↷ m. Let us consider the 2 n+1 states s 0 , . . . , s 2 n+1 -1 we can extract from this n times folded macro. With s 0 = I m I 505 and s i = s i-1 b i , where b i is the i-th base macro of m.Obviously, for each DDA heuristic h on Π there exists a choice of m I , ↷ m, m γ such that it holds:h(s 2•j ) > h(s 2•j+1 ) for all j ∈ [0, 2 n -1]Matching the first condition of the 2 n+1 state criterion.For the second condition we have to find a fitting partition 510 of V ≤n .We considerD m:n = {D m:n 0 , . . . , D m:n n } with D m:n n-i := {v ∈ V ≤n \ n j=n-i+1 D m:n j | creators(v) ∩ vars(eff( ↷ m n-i )) = ∅} with ↷ m n-i ∈ creases(m, n - i). These sets are obviously not intersecting. None of 515 them is empty because the meta-variable v n-i with creators(v n-i ) = {v 1 , . . . , v i-1 , v i+1 , . . . , v n } and v k ∈ vars(eff( ↷ m k )) (where ↷ m k ∈ creases(m, k)) is an element of D m:n n-i for each i ∈ [0, n]. Therefore, D m:n is a partition of V ≤n . 520 Looking at a sub-sequence of the base macros of m, focusing on the base macros [b g•2 d+1 +1 , . . . , b g•2 d+1 +2 d , . . . , b g•,2 d+1 -1 ] =: m d,g for an arbitrary d ∈ [0, n] and an arbitrary g ∈ [0, 2 n-d -1]. Since m is folded n times, the macro m d,g is folded d 525 times with b g•2 d+1 +2 d as d-th crease. With the Matching Lemma we conclude s g•2 d+1 +2 d -1-j b g•2 d+1 +2 d ! = s (g+1)•2 d+1 +2 d +j for all j ∈ [0, 2 d -1]. With index shift we get s g•2 d+1 +i b g•2 d+1 +2 d ! = s (g+1)•2 d+1 -1-i for all 530 i ∈ [0, 2 d -1].Since d and g were arbitrarily chosen it holds for all g ∈ [0, 2 n-d-1 ] and for all d ∈ [0, n].With the Orthogonality Lemma we see, that D m:n d does not contain any meta-variable created by a variable from vars(eff(b g•2 d+1 +2 d )) and projects the difference away.Therefore ∀d ∈ [0, n]∀g ∈ [0,2 n-d -1]∀i ∈ [0, 2 d -1] : s D m:n d g•2 d+1 +i = s D m:n d (g+1)•2 d+1 -1-iWe finally conclude that we can apply the 2 n+1 states criterion to reveal a correlation complexity of at least n + 1.The folded macro criterion with n = 1 is equivalent to the 535 criterion from Theorem 1.The 2 n states criterion and the folded macro criterion show sufficient conditions to detect a lower bound of the dimension of a potential heuristic. They do not answer the ques-540 tion if a planning task with arbitrary correlation complexity exists. In the following, we show that the answer is yes by applying the macro folding criterion on a Gray counter task with an arbitrary number n of bits.The Gray Counter Task with 3 bits is the example Seipp et al. (2016) provided with correlation complexity 3. It iterates through all binary numbers of a given length in an order such that consecutive numbers differ on only one bit, this is known as the Gray code (Gray 1953).Definition 6 (Gray Counter Task). The gray counter task of n bits is a planning task Π n = ⟨V n , I n , O n , γ n ⟩ with the state variables V n = {v 0 , . . . , v n-1 } with domain {0, 1}, the initial stateI n = {v i → 0|i ∈ [0, n -1]}, the operators O n = {⟨{v j → 0, v j-1 → 1} ∪ {v i → 0 | 0 ≤ i < j -1}, {v j → 1}⟩, ⟨{v j → 1, v j-1 → 1} ∪ {v i → 0 | 0 ≤ i < j -1}, {v j → 0}⟩ | 0 < j < n} ∪{⟨{v 0 → 0}, {v 0 → 1}⟩, ⟨{v 0 → 1}, {v 0 → 0}⟩} and the goal γ n = {v n-1 → 1} ∪ {v i → 0 | i ∈ [0, n -2]}.The task ⟨V, γ, O, I⟩ is a reverse gray counter task if ⟨V, I, O, γ⟩ is a gray counter task.We can also view it as a recursive construction. The gray counter task of 1 bit is a planning task Π = ⟨V, I, O, γ⟩ with 555 the state variables V = {v 0 } with domain {0, 1}, the initial state I = {v 0 → 0}, the operators O = {⟨{v 0 → 0}, {v 0 → 1}⟩, ⟨{v 0 → 1}, {v 0 → 0}⟩} and the goal γ = {v 0 → 1}.The gray counter task of n bits is a planning task Π with the state variables V = {v 0 , . . . , v n-1 } (each with domain {0, 1}) that consists of two tasks Π 1/2 , a gray counter task of size n-1 on the variables {v 0 , . . . , v n-2 } with an additional constant state variable v n-1 → 0 and Π 2/2 , a reverse gray counter task of size n -1 on the variables {v 0 , . . . , v n-2 } with an additional constant state variable v n-1 → 1. The initial state of Π is the initial state of Π 1/2 , the single goal state of Π is the single goal state of Π 2/2 and the operators of Π is the set containing:• each operator of Π 1/2 and Π 2/2 , • the operator with the goal state from Π 1/2 as precondi-570 tion and the initial state from Π 2/2 as effect and • the operator with the initial state from Π 2/2 as precondition and the goal state from Π 1/2 as effect. By looking at the Gray counter task through the lens of recursion it is clear what our macros have to be. We choose 575 -→ m to be the macro that solves Π 1/2 and ←m the macro that solves Π 2/2 , both have 2 n-1 -1 base macros, namely the original operators. They are obviously 2 n-1 -1-matching as they solve inverse problems. By the recursive construction of the gray counter task -→ m, ←m are both folded n-2 times. This fits the condition of the folded macro criterion and reveals a correlation complexity of n for the gray counter task on n bits. This shows that planning tasks of arbitrary correlation complexity do exist. Seipp et al. (2016) left an open question whether or not examples of "naturally occurring" planning domains that are tractable and contain tasks with high correlation complexity exist.If one ignores the tractable part the question can be answered with yes. Each domain that can directly encode a Turing Machine (TM) of arbitrary memory size has unbounded correlation complexity.What do we mean by encoding a finite tape Turing machine directly? Definition 7 (direct TM encoding). A TM is defined as ⟨Z, z 0 , z * , Γ, δ⟩ with Z the set of internal states, z 0 , z * ∈ Z where z 0 is the initial state and z * is the accepting state, Γ the set of tape symbols, and δ : (Z \ z * ) × Γ → Z × Γ × {-1, +1} the transition function.A planning task Π encodes a TM directly if it is solvable and• for each configuration c that TM traverses there is a corresponding landmark state s c , • if TM traverses c 1 before c 2 then each plan traverses s c1 before s c2 , and • there is a subset V tape of V such that:-s V \V tape c1 = s V \V tape c2for each configuration c 1 , c 2 that TM traverses and the internal state and the head position of c 1 and c 2 are the same.-Each variable in v ti ∈ V tape corresponds to a cell t i of the tape and for each c traversed by TM with symbol a in cell t i the state s c contains the fact v ti → d ti,a .Only TMs that halt can be encoded directly. The entry of a single cell could be encoded by multiple state variables in V tape but each v ∈ V tape encodes only one cell. Since V is finite the tape has to be finite, too. The initial state of the planning task encodes the initial configuration of the TM, including the input on the tape. Bylander (1994) described (in Theorem 3.1) a way to transform a TM into a planning task. This planning task encodes said TM directly.Consider a Turing machine that reads the input string, changes it to the next string according to the gray code, and sets the head back to the initial position. The machine repeats this until the final value of the gray code is represented by the tape. With an initial input of n-many 0's the correlation complexity of the task simulating such a Turing machine is at least n. This can be shown with the 2 n states criterion with the states that represent the Turing machine at the beginning of the described loop.Many domains of the International Planning Competition (IPC) enforce each task to have a correlation complexity of at most 2 (Seipp et al. 2016) . Culberson (1997) showed how to encode TMs into Sokoban tasks. This corresponds to a direct encoding, too. Helmert (2006) showed an encoding of TMs into Promela tasks. However, this encoding does not fit our definition. There the content of the cell at the position of the head and the position of the head is encoded in one variable and is therefore not a direct encoding. The partition of V is not possible. This is not the relevant hurdle, as we can still apply the Macro Folding Criterion on a Promela task that represents the described TM in Helmert's encoding. The two macros are putting the Promela-message that represents the TM symbol 1/0 into the Promela-queue that represents the cell which represents the second most significant bit on/off. The relevant hurdle is the PDDL encoding (Edelkamp 2003) as it allows to activate multiple Promela-transitions without executing them directly. This provides too much freedom to easily detect critical, matching macros.In the 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) Christen et al. (2023) encoded the independent set reconfiguration (ISR) problem as a planning task. The graph track asked for an instance with a long solution. They provided one that encodes a Gray counter. We can apply the macro folding criterion on this instance, too. This reveals a correlation complexity of at least n/5 for their graph track submissions, where n is the number of nodes in the instance graph.The earlier described Termes task has correlation complexity of at least 3. We discussed that the primary set-up and the primary tear-down are critical macros. They are 3-matching and folded once. With that, we can apply the macro folding criterion to confirm a correlation complexity of at least 3.This shows that we have occurrences of such domains (how natural these occurrences are is up to debate). Promela occurred in IPC4, Sokoban occurred in IPC6, ISR in the 1st CoRe Challenge, and Termes in IPC9.The original question about tractable domains remains open but with the Folded Macro criterion, we have a tool to show that a task has high correlation complexity.We were not able to find further IPC domains that allow tasks with a correlation complexity larger than 2. The way we found the ones we did was by constructing a task with only one (cycle free) solution. Without that, there is often some freedom (similar to the Promela domain) which hinders us from finding matching pairs of critical, folded macro.Lacking further examples of IPC domains where we can apply our new criterions might be a downside for their relevance, on the one hand. On the other hand, it indicates that potential heuristics are often sufficiently expressive even with low dimensions. The criterion gave further insight into what is challenging for potential heuristics but also provides a possible approach to tackle such challenges, namely with macros. Investigating planning based on macros (Jonsson 2009) seems to be a good candidate to accompany low dimensional potential heuristics. Planning based on macros is strong in the shortcomings of low dimensional potential heuristics.We found a generalization of the criterion from Theorem 1 for arbitrary correlation complexity. There might be a generalization to detect arbitrary correlation complexity for the criterion from Theorem 2, which incorporates dangerous operators. Such a criterion could provide further insight.The most significant difference between the Π ≤k construction and the P m construction by Haslum (2009) , the Π C compilation by Steinmetz and Hoffmann (2018) , or fluent merging by van den Briel, Kambhampati, and Vossen (2007) is that the Π C construction does not describe a valid planning task. The operators are not fitting to the resulting state space (it would be possible to extend the definition in a way 705 that we construct matching operators with metavariables in the precondition and effects. However, this would be rather cumbersome and unnecessary since we do not need the operators for our arguments).The additional variables in a Π C compilation have a bi-710 nary domain and each additional variable represents a partial assignment. In other words, a conjunction of facts. The metafacts in the Π ≤k construction represent a combination of facts. The domain of such a metavariable is the cartesian product of the corresponding domains. The set of partial as-715 signments that are considered by a Π C compilation, is not further specified. If C contains all partial assignments of size ≤ k, then we can interpret the additional facts from the Π C compilation as the translation into STRIPS of the additional facts from Π ≤k . 720 Fluent merging is defined on a finite domain representation and merging two variables combines their domains by a cartesian product like the Π ≤k construction. However, fluent merging replaces the variables it merges with the new one. Fluent merging reduces the number of state variables 725 while the Π ≤k construction increases the number of state variables.The P m construction is defined on propositional STRIPS tasks, while the Π ≤k construction and the Π C compilation are defined on tasks in finite domain representation. How-730 ever, the P m construction considers all partial assignments of size ≤ m and is in this regard similar to the Π ≤k construction.We have shown that the correlation complexity of a plan-735 ning task can be arbitrarily large. This means no fixed dimension for potential heuristics, in combination with simple hill climbing, will be sufficient for satisficing planning on arbitrary domains. It is in some cases possible to detect a large correlation complexity with the newly introduced 2 n states 740 criterion and Folded Macro criterion. We also showed that if a domain can encode a Turing machine in a certain way, then we can create tasks of arbitrary correlation complexity in this domain.With the new criterions, we gained a deeper understand-745 ing of what structure causes a large correlation complexity. 
introduction: 
 In classical planning, we try to find a plan, a sequence of actions to transition from an initial state to a goal state. We consider satisficing planning, which looks for a plan that leads us to a goal state. In contrast, optimal planning looks for the plan with the lowest cost. Both satisficing planning and optimal planning are PSPACE-complete in general (Bylander 1994) but for some domains, it is drastically easier to find a satisficing plan than to find an optimal one. Some satisficing planning tasks are easier to solve than others even though they have the same amount of variables 20 and operators. This difference is hidden somewhere in the structure of the task. The correlation complexity is one measures for the difficulty of a satisficing planning task.This measure is based on potential heuristics (Pommerening et al. 2015) , which looks at the features of a given state and sums their corresponding weight to compute a heuristic value.The correlation complexity of a task 1 Π describes the minimal dimension of a potential heuristic h pot such that h pot is descending and dead-end avoiding. This can be interpreted as a measure of how many facts the agent has to consider at once to find the next best successor. Unless all alive states are goal states the correlation complexity is at least 1 (the agent has to consider at least something).Finding the actual weights for such a potential heuris-35 tic is a hard problem and not the scope of this paper. It is PSPACE-complete in general and Σ p 2 -complete (that is the second level of the polynomial hierarchy) for heuristics with similar characteristics (Helmert et al. 2022 ). 1 In this work we assume that each task is solvable.In this work, we will introduce new criterions to detect a lower bound for arbitrary correlation complexity. Additionally, we prove the existence of planning tasks with arbitrary correlation complexity by applying the new criterion to gray counter tasks with an arbitrary number of bits.We consider classical planning in the SAS + formalism. A task Π = ⟨V, I, O, γ⟩ is a tuple, where V is the finite set of state variables in finite domain representation with the domain dom(v) for each v ∈ V . We call v → d with v ∈ V and d ∈ dom(v) a fact. A partial state p is a set of facts with pairwise different variables. We denote the variables mentioned by p as vars(p) := {v | v → d ∈ p}. A state s is a partial state containing all state variables (i.e. vars(s) = V ), we use the notation s ∈ Π to indicate that s is a state of the task Π. I is the initial state, and γ is a partial state indicating the goal of the task.The projection of a partial state s to the state variables W ⊆ vars(s) is denoted as sW := {v → d ∈ s | v ∈ W }.Each operator o = ⟨pre(o), eff(o)⟩ in O contains a precondition and an effect. Both of them are partial states. An operator o is applicable in state s if pre(o) ⊆ s. The successor of a state s and an applicable operator o is the state s o with s o vars(eff(o)) = eff(o) and s o V \vars(eff(o)) = s V \vars(eff(o)) . We use the notation s o! to forcefully apply operator o to state s, with s o! := s ⟨∅, eff(o)⟩ . We assume tasks to be in normal form, meaning vars(eff(o)) ⊆ vars(pre(o)) and eff(o) ∩ pre(o) = ∅ for each operator o ∈ O.We say two operators o, o ′ are inverse of each other if vars(eff(o)) = vars(eff(o ′ )), eff(o) ⊆ pre(o ′ ) and eff(o ′ ) ⊆ pre(o). Intuitively, everything changed by applying o to a state where it is applicable changes back by (forcefully) applying o ′ to that successor.A list of operators m = [o 1 , . . . , o n ] is called a macro, we treat them the same as operators with pre([o 1 , o 2 ]) = (pre(o 2 )eff(o 1 ))∪pre(o 1 ) and eff([o 1 , o 2 ]) = eff(o 2 )∪{v → d ∈ eff(o 1 ) | v / ∈ vars(eff(o 2 ))}\pre([o 1 , o 2 ]). Additionally, [o 1 , o 2 , o 3 , . . . , o n ] = [[o 1 , o 2 ], o 3 . . . , o n ] is a macro, too.We can recompose a macro by representing it as a different but equivalent list of macros and/or operators that keeps the same underlying list of operators.For example[[o 1 , o 2 , o 3 ], o 4 , [o 5 ]] can be recomposed into [[o 1 , o 2 ], [o 3 , o 4 ], [o 5 ]].We call the macros and operators in the outermost list the base macros.Applying a singleton macro Potential heuristics are a class of heuristics introduced by Pommerening et al. (2015) . A potential heuristic is a function h pot : P → R ∪ {∞} that is computed with a weighted count of the partial assignments that agree with the given 110 partial assignments.h pot (s) = p∈P (w(p) • [p ⊆ s])where P is the set of all possible partial assignments for the task, [p ⊆ s] is in the Iverson bracket notation, and w(p) is the weight for the partial assignment p. In practice, most of the weights are 0. The dimension of a potential heuristic is115 max p∈P,w(p)̸ =0 |p|.Correlation complexity is a measure of the complexity of planning tasks introduced by Seipp et al. (2016) which is based on potential heuristics. They looked for potential heuristics that are descending and dead-end avoiding (DDA). Definition 1 (Correlation Complexity). The correlation complexity of a planning task Π is defined as the minimal dimension of all descending, dead-end avoiding potential heuristics for Π. The correlation complexity of a domain is the maximal correlation complexity over all tasks in that domain.Finding a plan with the use of a DDA heuristic is easily done with simple hill-climbing. This algorithm works by starting at the initial state and repeatedly updating the current state with a successor that has a lower heuristic value until a goal state is found. This can be interpreted as wandering downwards in the state space. The number of state expansions is bounded by h pot (I) -min s∈S h pot (s) if all weights are integers (Seipp et al. 2016) .Seipp et al. investigated multiple IPC planning domains and showed that all of them had a correlation complexity of 2, but it is possible to construct planning tasks with correlation complexity of 3.We want to understand better what causes a large correlation complexity. Seipp et al. (2016) Theorem 1. Let Π be a planning task in normal form, and let o and o ′ be critical operators of Π that are inverses of each other. Then Π has correlation complexity of at least 2 Theorem 2. Let Π be a planning task in normal form, and let o be an operator that is critical and dangerous in Π. Then Π has correlation complexity of at least 2 These criterions focus on the operators in the task. We want to add criterions that look from a different angle and focus on the states instead.We introduce the quadruple criterion. Roughly speaking it checks if a given potential heuristic can be represented as a 2-dimensional heuristic. Note that any heuristic can be translated into a potential heuristic if the dimension is large enough.Theorem 3 (Quadruple Criterion). Let Π = ⟨V, I, O, γ⟩ be a planning task, and let h pot be a potential heuristic. If there exist states a, b, c, d in Π and a partition {W, M } of V such that:h pot (a) > h pot (b), a W = b W , a M = d M , h pot (c) ≥ h pot (d), c W = d W , b M = c M , then the dimension of h pot is at least 2.For the proof we use the fact that we can split one (finite) sum over all x ∈ X with a partition {Y, Z} of X into two sums where one iterates over y ∈ Y and the other over z ∈ Z. Assume that the dimension of the potential heuristic h pot is at most 1. The assumption implies thath pot (s) = p∈P,|p|≤1 w(p) • [p ⊆ s] = p∈P,|p|=1,vars(p)⊆W w(p) • [p ⊆ s W ]+ p∈P,|p|=1,vars(p)⊆M w(p)•[p ⊆ s M ]+w(∅) = h pot (s W ) + h pot (s M ) -w(∅)for each state s. The weight w(∅) is subtracted because ∅ ⊆ s W and ∅ ⊆ s M . This provides us with the two inequalitiesh pot (a W )+h pot (a M )-w(∅) > h pot (b W )+h pot (b M )-w(∅) h pot (c W )+h pot (c M )-w(∅) ≥ h pot (d W )+h pot (d M )-w(∅).Since a W = b W and c W = d W we can simplify the inequalities toh pot (a M ) > h pot (b M ) h pot (c M ) ≥ h pot (d M ).We know that a M = d M and b M = c M so we replace these values in the latest inequality and end up withh pot (a M ) > h pot (b M ) h pot (b M ) ≥ h pot (a M ).which is a contradiction. So the assumption is not true and therefore the dimension of the potential heuristic h pot is at least 2.The conditions of the quadruple criterion are sufficient to detect a dimension of at least 2. Is it also a necessary condition? The answer is no.Consider the two heuristics on a task with two variables of binary domain (with ′ XY ′ we denote the state{v 1 → X, v 2 → Y }): h 1 ( ′ 00 ′ ) = 0, h 1 ( ′ 10 ′ ) = 40, h 1 ( ′ 01 ′ ) = 2, h 1 ( ′ 11 ′ ) = 42 and h 2 which is equal to h 1 except for h 2 ( ′ 11 ′ ) > 42. It is easy to see that h 1 is of dimension 1 with w 1 (v 1 ) = 40, w 1 (v 2 ) =2 but h 2 is not. However, the order relations (>, ≥) are the same. Meaning, that if we could find an assignment of a, b, c, d, W, M for h 2 to detect its larger dimension by Theorem 4 we could use the same for h 1 , but that is not possible as h 1 is of dimension 1.We can use the quadruple criterion to argue about the correlation complexity.Theorem 4. Let Π = ⟨V, I, O, γ⟩ be a planning task. If for each potential heuristic h pot that is DDA on Π there exist states a, b, c, d in Π and a partition {W, M } of V such that:h pot (a) > h pot (b), a W = b W , a M = d M , h pot (c) ≥ h pot (d), c W = d W , b M = c M , then the correlation complexity of Π is at least 2.Note that these states and the partition do not have to be the same for all DDA potential heuristics.Proof. We know that the correlation complexity of a task Π is the minimal dimension over all potential heuristics that are DDA on Π. The condition of Theorem 4 implies that the quadruple criterion is applicable on each DDA potential heuristic on Π. Therefore, we can apply the quadruple criterion on each potential heuristic that is DDA on Π. We conclude that the dimension of each potential heuristic that is DDA on Π is at least 2. Therefore, the correlation complexity of Π is at least 2.Theorem 4 is a generalization of the criterion from Theorem 2 that Seipp et al. (2016) used to detect correlation complexity of at least 2 (proof in Appendix A). Theorem 3 is equivalent to the first (non-trivial) instance of a pattern, which we will call the 2 n states criterion. Here we formulate and prove it. Later, we will use the 2 n states criterion as a stepping stone to construct the macro folding criterion, a generalization of the criterion from Theorem 1. We then apply it to the family of Gray counter tasks and show that a Gray counter task has a correlation complexity equal to its number of bits. 
 
 Appendix:  


Decision: This paper introduce a new method for obtaining a lower bound on the correlation complexity of planning tasks - which is the minimum dimension of a potential heuristic necessary to solve the task without search. The paper provides strong theoretic contributions and analyses examples using the new lower bound.

The write-up of the paper should be improved for the final version. Especially the introduction and the "Turing Machine" section w.r.t. the discussion of what is a natural vs unnatural task should be rephrase to be more clear. Further, I would recommend that the authors include the examples and information given in their rebuttal into the paper.

I (and the reviewers) appreciate the author's detailed rebuttal.

Reviews: review: strength_weakness: strength_weakness: The paper organization is not ideal, as the contributions and structure of the paper is not communicated to the reader, so each new Section comes a bit as a surprise. For example, when reading the background, the reader is introduced to macros. But at that point is very unclear why macros would be relevant here.

An important part of this problem is the introduction, which does state some facts, but does not convey important information:
 * Motivation: The introduction says what correlation complexity is, but it does not say anything about why this is an interesting concept. The entire paper goes about how to show that there exist planning tasks with high correlation complexity. But, why should we care? Why is this finding interesting?

 * Contributions: The introduction does not say anything about what are the contributions of the paper. It would be important to mention that:
    - Seipp et al. already introduced a way to prove that tasks have a correlation complexity of at least 2.
    - This paper introduces new criteria. First, two criteria based on properties of the states. The quadruple criterion generalize the previous criteria being able to show correlation complexity of at least 2 in more cases. Then, the 2n criterion further generalizes the quadruple criterion to prove a correlation complexity of at least n.
      And then, new criteria based on the operators of the tasks are provided to avoid reasoning about a large amount of states. The new criteria are based on macros.
    - Then, we show a family of planning tasks and, using our criteria we show that correlation complexity grows with the task size, so there exist tasks with arbitrary correlation complexity.

 I'd have appreciated having some summary along those lines in the introduction so I'd recommend including that in the final version.



Technical correctness:

 * In Lemma 2, it is not mentioned that the task is in normal form, but that is assumed within the proof.

 * The proofs are slightly hard to follow and, while I understood the main arguments, I found hard to follow some of the details:

   - line 512: the proof uses the notation D^n:m. I don't understand the meaning of n:m, and given that n and m are used with many different meanings over the paper, perhaps they could be ommited here and just use D or other symbol?

   - In Theorem 7, it'd be nice to explain the partition that is used in the Termes example. As later it is mentioned that such partition exists but it is never provided.

   - In Definition 6, when j=0, the precondition v_{j-1} is not defined.

   - In the section "Turing Machine" several IPC domains are discussed. "Turing machine" is not a very good name for such a subsection. The claim saying that ISR instances have n/5 correlation complexity does not have  too many supporting arguments. Is this analyzed in more detail in some appendix?

 * In the discussion section, the paper says that the fact that the current criteria are not applicable indicates that low dimensions are sufficient in most domains. I don't think this is the case, as perhaps correlation complexity is high even if the criteria cannot prove it. Perhaps it'd be good to remind the reader the known results (for how many domains we know their correlation complexity is 1, 2, or > 2? for how many domains is the question still open?)

Minor comments:

- The plural of criterion is criteria.

- Line 23: 'measures' -> 'measure'.
- Line 76 '$pre(o_2)eff(o_1)$': a missing operator in between it seems. Also, why exactly is pre([o1,o2]) not a partial state?
- Line 90: 'might be no partial state' -> add 'called empty macro' or something like that,
  since 'non-empty macros' is used in the following sentence without defining it.
- Theorems 1 and 2 -> missing dot at the end.
- Line 259: `if $t \in l$`: $t$ and $l$ not defined.
- Table 1, line 282, line 285: Use `\mathit`, `\mbox` or something else in subindexes and 'free/full' for a better look.
- Line 285 (beginning of the page): '$v_robotHand$' -> '$v_{robotHand}$'.
- Line 286: 'contains 31 metafacts' -> it would be useful to specify how is this number computed. Also, some subset of the 31 facts is given, but it is not clarified that this is just an example. If there is a reason to include those as example and not others, it should be explicitly said.
- Line 287: '$v_{\langle\rangle} \mapsto \langle \rangle$' -> this notation has not been introduced.
- Definition 6: Readability would be increased by specifying preconditions and effects of operators separately.
questions: questions: What is the partition in the Termes example? Is it hard to lay out?
strength_weakness: strength_weakness: There are some issues that should be addressed for camera-ready. I will list
them mostly in order as they appear in the paper (severity of the issues is, I
think, self-evident):

Abstract should not use citations.

The notation X^V is never introduced. I could infer from the context that it
means restriction of a (partial) state X to variables V, but it should be
explicitly stated.

Definition of pre([o_1,o_2]) is missing set operator between pre(o_2) and
eff(o_1) -- I assume it should be pre(o_2) \setminus eff(o_1).
More importantly, macro is not well-defined, because it completely leaves out
the question of applicability of the sequence of operators it consists of (and
the application of operator/macro on a state is defined only for applicable
operators/macros). This should be explicitly defined. Either allow macros only
over sequences of operators that are applicable in the intermediate states, or
allow application of operators that are not applicable (it sounds weird, but one
could say that o applied on s is s[o] = s if pre(o) \not\subseteq s).

Page two, third paragraph: "The set pre([o_1,o_2]) might be no partial state."
I do not understand what it means. Maybe it has something to do with the issue
above? I guess if o_2 is not applicable after o_1, then
(pre(o_2) \setminus eff(o_1)) \cup pre(o_1) might contain two facts from the
same variable -- is this the case? If so, I suggest resolving it by simply
allowing only "meaningful" macros.

There is a mix-up between the definition of heuristic mapping *states* to
numbers, and potential heuristics mapping *partial states* to numbers. The
simplest solution I see is to define heuristics also over partial states and
then clearly explain why it is needed (after all, this would also make the
following text easier to understand).

Explain what Iverson bracket means -- I guess saying it is a notation for a
characteristic function would be enough.

Def. 1 defines correlation complexity for domains, but domains are never
formally introduced. In fact, a domain in this context is very informal concept
because correlation complexity reported for a domain (for example in
previous papers on correlation complexity) is not necessarily correlation
complexity over all possible tasks with the same PDDL domain. The reason is that
PDDL domains often allow to construct tasks that are not what the modeller had
in mind when writing the PDDL (that are not in the "spirit" of the domain). For
example, one could construct logisitics tasks where a truck is at multiple
locations at the same time as so on. In any case, this part should be removed
from the formal definition and moved to the text below as a sidenote (it's
actually not even important for the paper).

The paper could be improved with more examples, starting with examples for
Theorem 1 and 2. There seems to be enough space for it as some parts are
unnecessarily long (more on that below).

Page 2, last paragraph before the proof in right column. I do not see why waste
space for explaining to readers that sum over X is equal to sum of sums over its
partitions. It is so obvious that I would not include it at all -- I believe
every reader with a high-school diploma is able to figure this out.

The conditions in Theorem 3 and Theorem 4 are the same -- I suggest to give it a
speaking name or introduce a notation for it and then reuse it. It will not only
shorten the text, but it will also make it easier for the reader to match these
two theorems.

Proof of Theorem 3: The last step can be easily shortened to something like
Since a^M = d^M and b^M = c^m it follows that h^pot(a^M) > h^poy(b^M) \geq h^pot(a^M),
which is a contradiction.
There is also stray dot after h^pot(a^M).

Paragraph below the proof of Theorem 3: There is no need to pose rhetorical
questions, just state what you want to state: The quadruple criterion is
sufficient but not necessary condition...

Proof of Theorem 4 is unnecessarily long, because it is essentially just a
simple corollary of Theorem 3.

The title "2^n states criterion" should be capitalized.
There is no need for the first sentence of "2^n states criterion" subsection.

Def. 3:
 - Why is are subscripts of metavariables tuples instead of sets? The order of the
indexes does not matter (it matters for values though), and it would make more
clear that important is the combination of variables (not all orderings).

 - The definition meta^{\leq k}(s) should be
meta^{\leq k}(s) = \{meta_S(s) \mid S\subseteq V, |S|\leq k\}
not the \bigcup notation because meta_S(s) is a single pair (metafact).

 - "metafacts from s" does not make sense because there are no metafacts in s
   (s consists of facts).

 - shouldn't metafact be written as v \mapsto d instead of tuple <v,d>?

Last paragraph on page 3: It mentions constants -- they are not introduced nor
used in any way in the formalism. What do you mean by "without the constants"?

Isn't Lemma 1 unnecessarily weak? Unless I'm missing something, *for every*
potential heuristic of dimension k there exists a k-synchronized one of
dimension 1.

Theorem 5: \mathbb{N}_1 is not defined, I assume it suppose to mean
n\in\mathbb{N} and n >= 1. If so, please, write it as such.

All over the paper: I find it hard to read things like "n - 1-synchronized". I
think it would be easier to read if you used parenthesis: (n - 1)-synchronized.

Again, condition in Theorem 5 and Theorem 6 is the same -- please, give it a
name or introduce a notation for it (especially since it is very non-trivial
condition).
The proof of Theorem 6 is again unnecessarily long -- it is a simple corollary
of Theorem 5.

Def. 5: It is hard to distinguish arrow <- and -> above m because it's so small.
Could you use some notation that is easier to read?

Proof of Theorem 7: Please, replace "Matching Lemma" and "Orthogonality Lemma"
with Lemma 3 and 2, respectively. It would much easier to see what is referred.

The description of Gray Counter task says that the planning task \Pi consists of
two planning tasks \Pi_1/2 and \Pi_2/2. This is inaccurate (tasks here don't
consist of tasks), I guess what was meant by it is that \Pi can be decomposed
into two tasks \Pi_1/2 and \Pi_2/2.

The first sentence of "Turing Machine" section refers to the last sentence of
the previous section -- please, rephrase is.

I don't understand what is the point of the whole "Turing Machine" section.
It certainly does not answer the question about "naturally occurring" domains
with high correlation complexity. First, it is not clear what "naturally occurring"
actually means, so we can hardly try to answer this question on a formal
(technical) level. Second, TMs can encode any task, naturally occurring or not,
so I'm at loss what supposed to be point of this section. It definitely does not
make very convincing argument that there exist some kind of naturally occurring
tasks with high correlation complexity.
questions: questions: 1. Can Lemma 1 be strengthened as I mentioned before?

2. Can you comment on the "Turing Machine" section and explain what did you mean
by it?

3. Feel free to comment on anything else I mentioned in my review.

==== POST-REBUTTAL ===
Thank you for your responses.
Please, include in CR the changes you proposed in your responses to my and other reviews.

I would also suggest that you don't speak about "naturally occurring" domains and to be more clear/straightforward in the "Turing Machine" section. First, I don't think there is anything like "natural" domain. I certainly cannot imagine how would "unnatural" domain look like. Second, in the "Turing Machine" section you can simply argue that there are domains with unbounded correlation complexity like Sokoban, and then show that any domain that can encode the described TM will have unbounded correlation complexity. I think this is a decent contribution in its own right and there is no reason to confuse the reasoning by referring to some kind of natural domains.
strength_weakness: strength_weakness: The write-up is very dense and sometimes hard to follow. Several parts could benefit from a bit of polishing.
While I believe that all claims are correct, I could not follow all details of some of the later proofs.
In particular the indexing of the macro-folding part is quite challenging.
I think the paper could highly benefit from a few examples and intuitions.

In my opinion, the current related work section does not add much value. While the \Pi^<k construction is central to the paper, it is just
a supporting concept and not a main contribution of the paper. As such, I don't see why you compare it to the \Pi^C or \P^M constructions.
What I would find a lot more interesting (but optional) is in how far the results of this paper (in particular existence of tasks with high correlation complexity) are implied, or at least indicated, by some of the results of Pommerening et al AAAI'17, and Steinmetz&Hoffmann IJCAI'18.
Is there any connection to context-dependency graphs? Assuming there was a way to learn a set of minimal-size conjunctions that yields h*,
does the maximal size of any conjunction imply the correlation complexity?


Minor stuff:
- criterions --> criteria?
- line 76: missing \setminus
- line 93: marcos
- line 116: capital P in subscript should probably be \cal
- line 135: what is S?
- top left of page 4: subscript of v_{robothand}
questions: questions: 1) Line 207-210: I don't understand that sentence. Can you elaborate please.
2) Proof of theorem 7:
Why does the fact that \overleftarrow{m} and \overrightarrow{m} are both critical imply that they must appear in every plan?
From the definition of critical, there only needs to exist two alive states s,s' which are unsolvable without one of the two macros.
I don't see why s=s'=I.