Skip to main content
edited body
Source Link

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n$x$ be the input (length $n$) of  $M$, and $f(n)$$f(x)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n be the input of  $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let $x$ be the input (length $n$) of $M$, and $f(x)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

added 490 characters in body
Source Link

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n be the input of $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the definitionproposition of EXPTIME$A \in EXPTIME$?

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n be the input of $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the definition of EXPTIME?

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n be the input of $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the proposition of $A \in EXPTIME$?

added 490 characters in body
Source Link

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let $x_0 ... x_i$ denoten be the cellsinput of   $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the definition of EXPTIME?

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let $x_0 ... x_i$ denote the cells of $M$, which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.

Well, because this looks really like a homework question I give you the following hint:

What is PSAPCE exactly? How is "time" measured in sense of a turing computation? With these prerequesites, why is any problem, which is in PSPACE, "by definition" in EXPTIME?

Hope, I could give you some sketch

Edit (more hints): Okay, you have to be a bit more precise with your definitions: PSPACE is a set whereby, for all $A \in PSPACE$ there exists a Turing-Machine $M$, that can compute on an input $x$ with length $n$, if $x$ is a solution of the problem $A$ with at most using polynomial space on the turing working tape: Formal: Let n be the input of   $M$, and $f(n)$ shows the number of cells which are used (that means, the read/write head of $M$ visits this cell at least once) during the computation.
Then, there is $f \in \mathcal{O}(n^k)$ for one $k \in \mathbb{N}$ iff. $A \in PSPACE$

Now your exercise: What is the difference from EXPTIME in this definition? And why would any input (possible solution) $x$ (and its computation!) of a Problem $A \in PSPACE$ satisfy the definition of EXPTIME?

added 490 characters in body
Source Link
Loading
Source Link
Loading