{'fraction_non_alphanumeric': 0.04595952448344184, 'fraction_numerical': 0.009375884517407302, 'mean_word_length': 4.624875621890547, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Superlinear Lower Bounds Based on ETH

We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph's size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.


Motivation
Developing a deeper understanding of polynomial time problems is essential to the fields of algorithm design and computational complexity theory. In this work, we build on prior concepts from the topic of limited nondeterminism to show a new kind of conditional lower bound for polynomial time problems where a small runtime improvement for one problem would lead to a substantial runtime improvement for another.
We proceed by introducing basic notions and explaining how they relate to existing work. A polynomial time problem is a decision problem that can be decided in O(n k ) time for some constant k, where n denotes the input length. As usual, P denotes the class of polynomial time problems. A decision problem has an unconditional time complexity lower bound t(n) if it cannot be decided in o(t(n)) time. Polynomial time problems with unconditional superlinear time complexity lower bounds do not commonly appear in complexity theory research (aside from problems with lower bounds based on restrictive models such as one-tape Turing machines [24,34]). Such problems are known to exist by the deterministic time hierarchy theorem [23], but to the best of our knowledge, there are few examples that appear in the literature. Most of the known examples are related to pebbling games [3] or intersection non-emptiness for automata [39,41]. For these examples, the unconditional lower bounds are proven by combining Turing machine simulations with classical diagonalization arguments.
Although unconditional lower bounds are rare, many polynomial time problems have been shown to have conditional lower bounds in recent works on fine-grained complexity theory (see surveys [45,7]). Our primary goal is to introduce superlinear conditional lower bounds based on weaker hypotheses than existing works, by applying new relationships between deterministic and nondeterministic computations.

Our Contribution
In this work, all logarithms are base 2 and we say that a problem is solvable in essentially-linear time if it is decidable in O(n 1+ε ) time for all ε > 0.
The log-CircuitSAT decision problem (previously investigated in [8,2]) is a natural restriction of circuit satisfiability to bounded fan-in Boolean circuits with m gates and log(m) inputs. Like many problems in polynomial time, it is not currently known if unconditional superlinear time complexity lower bounds exist for log-CircuitSAT. We prove a superlinear conditional lower bound for log-CircuitSAT, as our main contribution. (Our conditional lower bound is in fact superquasilinear, where f is a quasilinear function if f (n)/n ∈ polylog(n).) In particular, we show in Theorem 22 that log-CircuitSAT is not decidable in essentially-linear time unless the Exponential Time Hypothesis (ETH) is false. This result is significant because existing works have only obtained conditional lower bounds for polynomial time problems based on the Strong Exponential Time Hypothesis (SETH). It is well known that SETH implies ETH but the reverse implication is not known to hold [16,Theorem 14.5]. In fact, it has been claimed that while ETH is plausible, SETH "is regarded by many as a quite doubtful working hypothesis that can be refuted at any time" [16, p. 470]. We therefore believe that a conditional lower bound for a natural polynomial time problem based on ETH instead of SETH represents significant progress.
As a further contribution, in Theorem 24 we show that log-CircuitSAT is not decidable in essentially-linear time unless k-Clique is decidable in essentiallylinear time in terms of the graph's size for all fixed k. This result is significant because the current best known algorithm for deciding k-Clique runs in O(v 0.792k ) time [40] where v denotes the number of vertices. Furthermore, showing that there exists a constant c such that k-Clique is decidable in O(v c ) time for all fixed k would constitute a major breakthrough.
Our results for log-CircuitSAT follow from Speed-up Theorems 12, 14, and 16.
These theorems show how a small runtime improvement for the deterministic simulation of nondeterministic machines with short witnesses would imply a substantial runtime improvement for the deterministic simulation of nondeterministic machines with large witnesses. Furthermore, these results advance our knowledge of limited nondeterminism by exploring possible trade-offs between time and witness length. Our techniques are straightforward adaptations of existing approaches to simulation; our contribution is a more detailed analysis of these simulations and how they behave when composed and iterated. This more detailed analysis is made possible by our novel approach to limited nondeterminism in Section 3.1.

Background
Let N denote the set of positive integers {1, 2, . . . }. The class of polynomial functions is and in a slight abuse of notation, we also sometimes use poly(n) to mean an arbitrary function from this class. We also refer to the class of polylogarithmic functions

Conditional Lower Bounds
Fine-grained complexity theory is a subject focused on exact runtime bounds and conditional lower bounds. A conditional lower bound for a polynomial time problem typically takes the following form: polynomial time problem A is not decidable in O(n α−ε ) time for all ε > 0 assuming that problem B is not decidable in O(t(n) β−ε ) time for all ε > 0, where α and β are constants and t(n) is a function (typically t(n) is either polynomial or exponential). This is referred to as a conditional lower bound because problem A has a lower bound under the assumption that B has a lower bound. Conditional lower bounds are known for many polynomial time problems including Triangle Finding, Orthogonal Vectors Problem (OVP), 3SUM, and All Pairs Shortest Path (APSP) [45,7].

Exponential Time Hypothesis
Decision problems related to Boolean formulas have been significant to the study of computational hardness [13,32]. As a result, satisfiability of Boolean formulas (SAT) is a natural candidate for lower bound assumptions. In particular, it is common to focus on satisfiability of Boolean formulas in conjunctive normal form with clause width at most k (denoted by k-CNF-SAT) for a fixed k.
The exponential time hypothesis (ETH) states that there is some ε > 0, such that 3-CNF-SAT cannot be decided in poly(n) · 2 ε·v time, where n denotes the input size and v denotes the number of variables [26]. The strong exponential time hypothesis (SETH) states that for every ε > 0, there is a sufficiently large k such that k-CNF-SAT cannot be decided in poly(n) · 2 (1−ε)·v time [26,27,11].
Conditional lower bounds are frequently shown relative to k-CNF-SAT. For instance, it is well known that the Orthogonal Vectors Problem (OVP) on polylogarithmic length vectors is not decidable in O(n 2−ε ) time for all ε > 0 assuming SETH [42,45,7].
Remark 1. As far as we know, the current best reduction shows that an O(n α ) time algorithm for OVP would lead to a poly(n) · 2 α·v 2 time algorithm for k-CNF-SAT for all k [42,45,7]. This isn't sufficient to show a lower bound conditional on ETH. Furthermore, we do not know if the existence of an essentially-linear time algorithm for OVP would imply that ETH is false.

Limited Nondeterminism
A nondeterministic polynomial time problem is a problem that can be decided in polynomial time by a nondeterministic machine. Nondeterminism can appear in a computation in multiple different ways. For instance, a machine could have nondeterministic bits written on a tape in advance, or could make nondeterministic guesses during the computation. Such variations do not appear to make much difference for nondeterministic polynomial time (NP). However, the definitions do require special care for notions of limited nondeterminism, which refers to the restriction or bounding of the amount of nondeterminism in a computation.
We proceed by reviewing some prior models of limited nondeterminism. Consider a machine model consisting of a multitape Turing machine with a special guess tape; all the remaining tapes are standard. In this model, the number of bits of nondeterminism used by the machine is the number of cells of the guess tape that are accessed by the machine during a computation, multiplied by the number of bits represented by each cell. The contents of the guess tape are referred to as the witness.
Kintala and Fischer [29,30] defined P f (n) as the class of languages that can be decided by a polynomial time bounded machine which scans at most f (n) cells of the guess tape for each input of size n. Note that this concept uses an exact limit for the amount of nondeterminism. Abandoning this exactness, Alvarez, Díaz and Torán [4,17], making explicit a concept of Xu, Doner, and Book [35], then defined β k as the class of languages that can be decided by a polynomial-time bounded machine which uses at most O((log(n)) k ) bits of nondeterminism. Farr took a similar approach [18], defining f (n)-NP as the languages that can be decided by a polynomial-time bounded machine which scans at most f (q(n)) cells of the guess tape for each input of size n. Here q is a polynomial that depends only on the machine, so again there is an unspecified constant factor allowed in the amount of nondeterminism. Note that f (n)-NP is the union over all k of the classes P f (n k ) . Another related approach was taken by Buss and Goldsmith [8] where N m P l is defined as the class of languages decided by nondeterministic machines in quasi-n l time making at most m · log(n) nondeterministic guesses. In this approach the limit on the amount of nondeterminism is exact, but arbitrary poly-logarithmic factors are allowed in the time bound. Finally, in the survey by Goldsmith, Levy and Mundhenk [21] the β k classes were then extended to verifiers other than those with a polynomial time bound. In this notation, β k −C is defined relative to a complexity class C that bounds the power of the verifier. Therefore, we have Taking a slightly different approach, Cai and Chen [10] focused on machines that partition access to nondeterminism, by first creating the contents of the guess tape, and then using a deterministic machine to check this guess. In this terminology, GC(s(n), C) is the class of languages that can be decided by a machine that guesses O(s(n)) bits and then uses the power of class C to verify. Again an arbitrary constant factor is allowed in the number of nondeterministic bits, to allow classes to contain complete languages.
Santhanam [38] then returned to a definition that uses an exact limit for the amount of allowed nondeterminism: NTIGU(t(n), g(n)) is the class of languages that can be decided by a machine that makes g(n) guesses and runs for O(t(n)) time. These classes have also been denoted NTIMEGUESS(t(n), g(n)) in a more recent work [20].
It follows from the definitions that Furthermore, the β k classes are meant to capture classes between P and NP.
Remark 2. In this work, we focus on the log-CircuitSAT problem and the levels within P = β 1 . It is worth noting that a loosely related work [19] investigated the log-Clique problem which is in β 2 = NTIGU(poly(n), O(log(n) 2 )).

Time-Witness Trade-offs
In the following, we introduce a new notion of limited nondeterminism that we use to prove new relationships between deterministic and nondeterministic computations. In particular, we prove that if faster deterministic algorithms exist, then there are straightforward trade-offs between time and witness length. For our notion of limited nondeterminism, unlike existing models, the nondeterministic guesses are preallocated as placeholders within an input string. These placeholders can then be filled with nondeterministic bits. It is important to note that different models of limited nondeterminism could be used. However, our model allows us to preserve the input size enabling us to prove technical results, Lemmas 9 and 10. Attempting to prove a result like Lemma 9 for a model such as NTIGU introduces unnecessary challenges with managing input and guess strings.

A New Model for Limited Nondeterminism
The attempts at constructing robust classes containing complete problems by allowing arbitrary factors in the amount of nondeterminism were challenged by the various downward collapses of the β hierarchy shown by Beigel and Goldsmith relative to oracles [5]. We therefore need a notion of limited nondeterminism that tracks constant factors in the amount of nondeterminism, accepting a lack of complete problems in our complexity classes to gain greater precision in reductions. This suggests using the NTIGU notation. However, we found that attempting to use the NTIGU notion directly leads to difficulties with bookkeeping when composing multiple reductions because of the necessary simultaneous management of input and guess strings. Since composing reductions is at the heart of our approach for proving speed-up theorems in Subsection 3.3, we sought a different notion that overcomes these unnecessary technical obstacles.
We now introduce our model of limited nondeterminism which allows us to be more explicit than the NTIGU classes in keeping track of the witness bits when composing reductions. Reminiscent of the Cai and Chen guess-andcheck classes, in our model the nondeterministic guesses will be preallocated as placeholder characters within an input string. This means that we can only fill in placeholder characters with nondeterministic bits. This property is essential for proving structural properties (see the translation and padding lemmas in Subsection 3.2). With other models, proofs of structural properties appear to be intrinsically more complex, requiring separate treatment of various overheads and applications of tape reduction theorems.
Consider strings over a ternary alphabet Σ = {0, 1, p} where p is referred to as the placeholder character. We index the bits of a string starting from position 0. For any string x ∈ Σ * , we let |x| denote the length of x and # p (x) denote the number of placeholder character occurrences in x.
Definition 3. Let a string r ∈ {0, 1} * be given. Define a function sub r : Σ * → Σ * such that for each string x ∈ Σ * , sub r (x) is obtained from x by replacing placeholder characters with bits from r so that the ith placeholder character from x is replaced by the ith bit of r for all i satisfying 0 ≤ i < min{|r|, # p (x)}. Also, define SUB(n) := { sub r | |r| ≤ n }. We call sub r a prefix filling and SUB(n) a set of prefix fillings. A prefix filling sub r replaces the first |r| placeholder characters with the bits of r in order (from the least index to the greatest). If there are fewer placeholder characters then some of the bits of r remain unused. We also consider the notion of an unrestricted filling, which is any injective replacement of placeholder characters, without specifying the particular order.

Definition 5.
For strings x and y ∈ Σ * , we write x y if x can be obtained from y by replacing any number of placeholder characters in y with 0 or 1. Given a language L ⊆ Σ * , we let the closure of L under unrestricted fillings be Example 6. Consider a language L = {0p1p}. By applying the preceding definition, we have that Clo(L) = {0p1p, 0p10, 0p11, 001p, 011p, 0010, 0011, 0110, 0111}.
In the following, DTIME(t(n)) represents the class of languages decidable in O(t(n)) time by multitape Turing machines that have read and write access to all tapes (including the input tape). We proceed by defining a complexity class DTIWI(t(n), w(n)) where intuitively t(n) represents a time bound and w(n) represents a bound on witness length. if there exist languages U and V ⊆ Σ * satisfying the following properties: • U ∈ DTIME(n), • Clo(U ) ∈ DTIME(n), • V ∈ DTIME(t(n)), and • for all x ∈ Σ * , x ∈ L if and only if x ∈ U and there exists s ∈ SUB(w(|x|)) such that s(x) ∈ V .
We refer to V as a verification language for L with input string universe U .
There are many different ways to encode structures as strings over a fixed alphabet, so decision problems can take many different forms as formal languages. To put a problem within DTIWI(t(n), w(n)), we therefore need to provide an encoding for its inputs with placeholder characters at the appropriate positions.
Example 8. SAT can be represented such that each input has placeholder characters out front followed by an encoding of a Boolean formula. Each variable is represented as a binary number representing an index to a placeholder. The placeholders will be nondeterministically filled to create a variable assignment.

Structural Properties of Limited Nondeterminism
The following two lemmas demonstrate structural properties relating time and witness length. These properties will be essential to proving speed-up theorems in Subsection 3.3 that reveal new relationships between deterministic and nondeterministic computations.
Let a function w be given. Let L ∈ DTIWI(t(n), w(n) + w (n)) be given. By definition, there exist an input string universe U and a verification language V ∈ DTIME(t(n)) satisfying that ∀x ∈ Σ * , x ∈ L if and only if x ∈ U and there exists s ∈ SUB(w(|x|) + w (|x|)) such that s(x) ∈ V . Consider a new language By interpreting V as a verification language for L with input string universe Clo(U ), we get L ∈ DTIWI(t(n), w(n)). By assumption, it follows that L ∈ DTIME(t (n)).
Finally, by interpreting L as a verification language for L with input string universe U , we get L ∈ DTIWI(t (n), w (n)).
Recall that a function f : N → N is fully time-constructible if there is a deterministic multitape Turing machine M that for every input of length n runs for exactly f (n) steps [25]. By convention, if f (n) is a fully time-constructible function, then f (n) ≥ n for all n ∈ N.
Proof. Suppose that DTIWI(t(n), w(n)) ⊆ DTIME(t (n)), and that f : N → N is fully time-constructible. By definition, there exist an input string universe U and a verification language V ∈ DTIME(t(f (n))) so that ∀x ∈ Σ * , x ∈ L if and only if x ∈ U and there exists s ∈ SUB(w(f (|x|))) such that s(x) ∈ V . Consider new languages L , V , and U such that Since V ∈ DTIME(t(f (n))), we have that V ∈ DTIME(t(n)). By interpreting V as a verification language for L with input string universe U , we get L ∈ DTIWI(t(n), w(n)). By assumption, it follows that L ∈ DTIME(t (n)). We conclude that L ∈ DTIME(t (f (n))).
Remark 11. Initially, we tried to use other notions of limited nondeterminism such as NTIGU to prove the preceding lemmas. However, the proofs were messy and required increasing the number of Turing machine tapes or the time complexity. In contrast, our model for limited nondeterminism (DTIWI) preserves the input size leading to straightforward proofs with tighter complexity bounds.

Speed-up Theorems
In this subsection, we carefully prove three speed-up theorems relating time and witness length. It is important to mention that there are existing speed-up theorems in the recent literature relating different computational resources such as those relating time and space in [43,9] and relating probabilistic circuit size and success probability in [36]. In addition, although relevant, we note that our speed-up results are distinct from recent hardness magnification results [12] which amplify circuit lower bounds rather than speed up computations.
The first speed-up theorem follows by repeatedly applying the structural properties of limited nondeterminism from the preceding subsection.
It follows that DTIWI(n, (Σ k+1 i=0 α i ) log(n)) ⊆ DTIME(n α k+2 ). Remark 13. Theorem 12 is a speed-up result because when 1 ≤ α < 2, the exponent from the runtime divided by the constant factor for the witness string length decreases as k increases. In particular, we have The second speed-up theorem follows by combining the first speed-up theorem with the padding lemma. We say that a function g : N → N is wellcomputable if g(n) ≤ n for every n ∈ N, g(n) = ω(log(n)), and g(n) can be computed in poly(n) steps.
Proof. Follows directly from Theorem 14.
The third speed-up theorem follows by carefully applying the first speed-up theorem.
As the rationals form a dense subset of the reals, the result follows.

log-CircuitSAT Decision Problem
A common generalization of SAT is the problem of deciding satisfiability of Boolean circuits (denoted by CircuitSAT). There is a natural restriction of CircuitSAT to bounded fan-in Boolean circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) [8,2]. We encode this problem so that the placeholder characters are out front followed by an encoding of a bounded fan-in Boolean circuit. Such an encoding can be carried out so that if n denotes the total input length and m denotes the number of gates, then n = Θ(m · log(m)).
The log-CircuitSAT decision problem is decidable in polynomial time because we can evaluate the circuit on every possible input assignment. Whether or not we can decide log-CircuitSAT in O(n 2−ε ) time for some ε > 0 is an open problem. Furthermore, as far as we know, no unconditional superlinear lower bounds are known for log-CircuitSAT. Later in this section, we prove a superlinear conditional lower bound for log-CircuitSAT. In particular, we show that if log-CircuitSAT is decidable in essentially-linear time, then ETH is false (Theorem 22) meaning that a small runtime improvement for log-CircuitSAT would lead to a substantial runtime improvement for NP-complete problems.

Simulating Turing Machines Using Boolean Circuits
Let a fully time-constructible function t be given. Any O(t(n)) time bounded Turing machine can be simulated by an oblivious Turing machine in O(t(n) · log(t(n))) time [37]. Moreover, any O(t(n)) time bounded Turing machine can be simulated by Boolean circuits of size O(t(n) · log(t(n))) which can be computed efficiently by a Turing machine [14]. Theorem 17 ([37,14,8,28]). Let a fully time-constructible function t be given. If L ∈ DTIME(t(n)), then in O(t(n) · poly(log(t(n)))) time, we can compute Boolean circuits for L of size at most O(t(n) · log(t(n))).
We now use Theorem 17 to show that any problem in DTIWI(n, log(n)) is efficiently reducible to log-CircuitSAT.
Theorem 18. Any L ∈ DTIWI(n, log(n)) is reducible to logarithmically many instances of log-CircuitSAT in essentially-linear time by a Turing machine.
Proof. Let L ∈ DTIWI(n, log(n)) be given. Let V ∈ DTIME(n) denote a verification language for L with input string universe U ∈ DTIME(n).
Let an input string x ∈ U of length n be given. By Theorem 17, we can compute a Boolean circuit 1 C for V with at most O(n · log(n)) gates in essentially-linear time on a Turing machine. In the following, let [log(n)] denote {1, 2, . . . , log(n) }. Now, we construct a family of circuits {C i } [log(n)] such that for each i ∈ [log(n)], C i is obtained by fixing the characters of x into the circuit C so that only i input bits remain where these input bits are associated with the first i placeholders within x. Therefore the circuit C i has at most log(n) inputs and at most O(n · log(n)) gates. It follows that x ∈ L if and only if there exists i ∈ [log(n)] such that C i is satisfiable.
Proof. Follows directly from Theorem 18.

ETH-hardness
We combine results from Subsection 4.2 with the Second Speed-up Theorem to prove superlinear conditional lower bounds for log-CircuitSAT. In particular, existence of essentially-linear time algorithms for log-CircuitSAT would imply that ETH is false.
Proof. Follows by combining Corollary 19 with Corollary 15.
We now relate log-CircuitSAT and CircuitSAT, showing that an essentiallylinear upper bound for log-CircuitSAT would imply a subexponential upper bound for CircuitSAT.
Recall that we encode Boolean circuits so that n = Θ(m · log(m)) where m is the number of gates. Therefore, n log(n) is Θ(m). Also, under reasonable encoding conventions, n log(n) will actually be larger than the number of gates and inputs. (Note that one could always scale up the witness size by a rational constant factor if needed.) Hence, CircuitSAT ∈ DTIWI(poly(n), n log(n) ).
We now show that log-CircuitSAT cannot be decided in essentially-linear time unless ETH fails. Note that this is a conditional lower bound based on ETH rather than the more common (and stronger) SETH assumption.

Hardness for k-Clique
We combine results from Subsection 4.2 with the Third Speed-up Theorem to prove that the existence of essentially-linear time algorithms for log-CircuitSAT would imply that k-Clique has essentially-linear time algorithms for all fixed k.
It is important to note that our construction is non-uniform meaning that we obtain differing algorithms that cannot necessarily be combined into a single efficient approach for solving k-Clique on non-constant k. As a result, our argument is not sufficient to conclude FPT = W [1].
Proof. Follows by combining Corollary 19 with Theorem 16.
From this, we are able to obtain a meaningful connection between the log-CircuitSAT and k-Clique problems.
Proof. The variable n denotes the total length of the graph's encoding which is Θ((v + e) · log(v)) where v is the number of vertices and e is the number of edges. We observe that for all fixed k, we have k-Clique ∈ DTIWI(n, k · log(n)).
We combine this observation with Corollary 23 to obtain the desired result.
Remark 25. Although we do not focus on parameterized complexity theory here, the preceding arguments can also be used to show that if log-CircuitSAT is decidable in essentially-linear time, then W[1] ⊆ non-uniform-FPT. Moreover, we suggest that this implication could be extended to W[P] ⊆ non-uniform-FPT. We refer the reader to [2] for background on W[P] and the W hierarchy.

Conclusion
We have demonstrated superlinear conditional lower bounds for the log-CircuitSAT decision problem by carefully investigating properties of limited nondeterminism. In particular, in Theorem 22 we showed that the existence of essentiallylinear time Turing machines for log-CircuitSAT would imply that ETH is false. This means that a small runtime improvement for log-CircuitSAT would lead to a substantial runtime improvement for NP-complete problems. Through this investigation we revealed new relationships between deterministic and nondeterministic computations. We leave two important questions unanswered that we hope will inspire future work. Question 26. Would the existence of essentially-linear time random access machines for log-CircuitSAT imply that ETH is false? This question is related to whether linear time for random access machines can be simulated in subquadratic time by multitape Turing machines [15]. It is also related to whether random access machines can be made oblivious [22]. Question 27. Can the construction from the first speed-up theorem (Theorem 12) be carried out for a non-constant number k of iterations? We speculate that if it can, then DTIWI(n, log(n)) ⊆ DTIME(n · log(n)) would imply that NTIME(n) ⊆ DTIME(2 √ n ).
In addition, although this work does not focus on circuit lower bounds, we suggest that recent results connecting the existence of faster algorithms with circuit lower bounds [1,44,43,6] could be applied to show that the existence of faster algorithms for log-CircuitSAT would imply new circuit lower bounds for E NP as well as other complexity classes.
Finally, we leave the reader with the thought that the speed-up theorems for limited nondeterminism (Theorems 12, 14, and 16) might be special cases of a more general speed-up result connecting nondeterminism, alternation, and time.