I don’t know this is a proper question on this forum but I was reading about computability theory and I saw the reduction concept and its notation like this: $ A \le_pB$ . I just wanted to know is this notation can be reversed? that is, can I write this down like $ A\ge_p B$ And still have a meaning? I searched a lot but this notation always been like the former and I got confused.

# Tag: reduction

## Is this general form of Von Neumann’s reduction postulate correct?

I have had a look at a book on ‘Quantun Measurement’ by Braginsky and Khalili$ ^1$ . In it appears an equation that I would like confirmation of. The equation seems odd, in that it sets a probability for the result of a measurement to the trace of some matrix.The equation in question is (2.7) ,see the book, Section 2.5 ‘von Neumann’s postulate of reduction’. I quote

$ $ w_n=Tr(|q_n\rangle\langle q_n|\hat{\rho}_{init}) \tag{2.7}$ $

My question is. Is (2.7) correct?

Reference

1) Vladimir B Braginsky and Farid Ya Khalili, Quantum Measurement, Ed Kip S Thorne, Cambridge University Press, First paperback edition (with corrections) 1995.

**Other Info**

In the book the second part of the general form of the postulate is (2.8), this applies to the density matrix asociated with the state of the system after measurement, it is

$ $ \hat{\rho}_n = \frac{1}{w_n} |q_n\rangle\langle q_n| > \hat{\rho}_{init} |q_n\rangle\langle q_n| \tag{2.8}$ $

(2.7) is supposed to apply to a quantum system which is initially in a state with associated density operator $ \hat{\rho}_{init}$ . The system may consist of two particles (or I assume an arbitrary number). In it, $ w_n$ is the probability of obtaining the result of measurement $ q_n$ , for an observable $ q$ with an associated operator $ \hat{q}$ , this operator has a discrete set of eigenvalues.We have $ $ \hat{q} |q_n\rangle= q_n |q_n\rangle $ $ The book also has the one degree of freedom version of von Neumann’s postulate, in this the probability of a measurement is given in (2.6) as

$ $ w_n=\langle q_n|\hat{\rho}_{init}|q_n\rangle \tag{2.6}$ $

## Intersection of reductions is a reduction

Let $ (R, \mathcal{m},K)$ be local ring with $ J_0\supseteq J_1 \supseteq J_2\supseteq \cdots$ are all reductions of I. Then, $ \bigcap_nJ_n$ is also a reduction of I.

I have done.

I take the family $ \{\frac{J_i+\mathcal{m}I}{\mathcal{m}I}\}$ . Each element has finite dimention as vectoral space over $ K$ . Then, there exists $ N$ nonnegatibe integer such that $ \frac{J_N+\mathcal{m}I}{\mathcal{m}I}=\frac{J_i+\mathcal{m}I}{\mathcal{m}I}$ for $ i \geq N$ , and so $ J_N+\mathcal{m}I=J_i+\mathcal{m}I$ for $ i \geq N$

## Mapping reduction for the useless state problem to prove that its undecidable

I want to give a mapping reduction (many-to-one) using the Empty_TM which accepts nothing, so the accept state is a useless state. This is to show that useless_TM is undecidable.

A state q in a TM M is said to be useless if this state is never reached when M is executed on any string ω ∈ Σ*.

**Note: I want the description of the reduction and not the computable function f: Σ* –> Σ***

## Structures on the spaces of geodesics and symplectic reduction by non-compact groups

Let $ X$ be a complete Riemannian manifold and suppose its space of geodesics $ M$ is a manifold (orbifold). Then $ M$ can be constructed as the symplectic reduction of $ TX$ by the geodesic flow. Notice that the trivial one-point “geodesics” give us an embedding $ X\to M$ . The symplectic structure on $ TX$ comes from the isomorphism with $ T^*X$ . The general Marsden-Weinstein machinery works only for symplectic reduction by compact groups as I understand so

In which cases the symplectic structure on $ TX$ descends to $ M$ ?

Now we also know that a neighbourhood of $ X$ in $ TX$ (which we can assume invariant under geodesic flow) admits a natural Kähler structure (see Guillemin-Stenzel or Lempert-Szöke) so it might happen that the Kähler reduction gives us a natural Kähler structure on $ M$ .

In which cases the Kähler structure on a neighbourhood of $ X$ in $ TX$ descends to a neighbourhood of $ X$ in $ M$ ?

## Proof of Karp Reduction being closed under coNP

Is it true that $ A \leq_k B \land B \in coNP \implies A \in coNP$ ?

If so, how would you go about proving it?

## finding a map reduction from $A_{TM}$ to $\overline{CF_{TM}}$

i am sitting for quite a while trying to find a mapping reduction finding a map reduction from $ A_{TM}$ to $ \overline{CF_{TM}}$ , and i can’t seem to find a reduction to the complement ($ \overline{CF_{TM}}$ )

(Definition: $ CF_{TM}\:=\:\left\{<M> |\:M\:is\:a\:TM\:and\:L\left(M\right)\:is\:a\:context\:free\:language\right\}$ )

$ A_{TM}=\left\{<M,w>|\:M\:is\:a\:Turing\:Machine\:description\:and\:w\:\in \:L\left(M\right)\:\:\right\} $

the mapping reduction of the regular(not the complimentary afaik is: $ <M,w> \in A_{TM}$ iff we can construct a language L that will be a context free language in the following way: $ L(F((<M,w>)))$ should be a context free language.

but i don’t know how to construct a mapping reduction for the complimentary, i.e $ A_{TM}$ to $ \overline{CF_{TM}}$ .

would really appreciate assistance with it.

thank you very much

## Mod p reduction of geometrically irreducible polynomials

Let $ f\in \mathbb Z[t,x]$ be a polynomial of positive degree that is irreducible over $ \overline{\mathbb Q}[t,x]$ . Is it true that for all but finitely many primes $ p$ the reduced polynomial $ f_p\in \mathbb F_p[t,x]$ is irreducible over $ \overline{\mathbb F}_p[t,x]$ ? If yes, is there a way to determine all the finitely many primes for which this does not happen?

## Prove that NP is closed under karp reduction?

A complexity class $ \mathbb{C}$ is said to be closed under a reduction if:

$ A$ reduces to $ B$ and $ B \in \mathbb{C}$ $ \implies$ $ A \in \mathbb{C}$

How would you go about proving this if $ \mathbb{C} = NP$ and the reduction to be the karp reduction? i.e.

Prove that if $ A$ karp reduces to $ B$ and $ B \in NP$ $ \implies$ $ A \in NP$

## P Langauage to NP Reduction in Polynomial Time

Let L be a language in P. Prove it is polynomial time reducible to any language in NP, including any language in P, which contains at least one string but doesn’t contain all the strings.

I tried solving this, One solution I can think of is making a deterministic Turing machine that recognizes the problem P in polynomial time and then I can convert the Turing machine into a non-deterministic machine but that will that exponential time. Can we do a conversion in polynomial time?