Reference no: EM132693790
1. Prove each of the following. You may use any of the theorems stated in the lecture notes and homework assignments.
a. If A ∈ PSPACE-Complete, B ∈ PSPACE, and A ≤p B, then B ∈ PSPACE-Complete.
b. If there exists A ∈ PSPACE - NP, then for all L ∈ PSPACE-Complete, L ∉ NP.
c. For any A, B ∈ PSPACE-Complete, A ≤p B and B ≤p A.
d. Co-NP ⊆ PSPACE. (Co-NP is defined in this note.)
2. Let
ψ(x1, x2, x3) = (¬x1 ∨ x2 ∨ ¬x3) ∧ (x1 ∨ ¬x2 ∨ x3)
a. Give an evaluation tree for ψ by assigning xi = 0 and 1, 1 ≤ i ≤ 3. You may terminate a branch as soon as its value is known.
b. For each of the following formulas, decide if it is true or false and which player (E or A) has a winning strategy. Justify your answers based on the evaluation tree built in (a).
i. ∃x1∀x2∃x3ψ(x1, x2, x3)
ii. ∀x1∃x2∀x3ψ(x1, x2, x3)
iii. ∃x1∀x2∀x3ψ(x1, x2, x3)
3. Consider QBFs:
Q1x1Q2x2 ··· Qkxk ψ(x1, ..., xk)
a. There is a type of ψ(x1, ..., xk) such that, regardless of what quantifiers Q1, Q2, ..., Qk are, player E always wins no matter what values it and player A select in their turns. What type of formula is it? Justify your answer.
b. There is a type of ψ(x1, ..., xk) such that, regardless of what quantifiers Q1, Q2, ..., Qk are, player A always wins no matter what values it and player E select in their turns. What type of formula is it? Justify your answer.
|
Which the budget schedule that provide necessary input data
: individual budget schedules are prepared. The budget schedule that would provide the necessary input data for the direct labor budget would be the
|
|
Discuss about the political uses of evaluations
: Evaluators need to have a realistic understanding of the context of evaluations, the political uses of evaluations, and the conditions under which information.
|
|
Which among the components of the master budget
: Among the components of the master budget in the selling and administrative budget, which? should be detailed so that key assumptions can be better understood
|
|
What the last budget schedule prepared
: Continues through the preparation of the budgeted financial statements. The last budget schedule prepared before the financial statements is the
|
|
Evaluation tree built in
: Give an evaluation tree for ? by assigning xi = 0 and 1, 1 = i = 3. You may terminate a branch as soon as its value is known.
|
|
What budgeted peso sales for peter senen inc initial year
: Peter Senen, Inc., The product will be sold for P20 per unit. The budgeted peso sales for Peter Senen, Inc's initial year of operations is
|
|
What the budgeted sales revenue based on the expected number
: Ethel Corporation, What the budgeted sales revenue based on the expected number of pieces of push-button switches to be sold in 2021 is
|
|
Conduct your own research to develop your recommendations
: For this Discussion, review this week's resources or conduct your own research to develop your recommendations. Ann Executive Summary (single spaced, no more).
|
|
How many pieces of materials should the company plan
: JYD Company has budgeted sales of P90,000 units in January. How many pieces of materials should the company plan to purchase in January?
|