text:
Approximating E3-LIN is NP-Hard

This lecture, which I gave for my 18.434 seminar, focuses on the MAX-E3LIN problem. We prove that approximating it is NP-hard by a reduction from LABEL-COVER.

1. Introducing MAX-E3LIN

In the MAX-E3LIN problem, our input is a series of linear equations ${\pmod 2}$ in ${n}$ binary variables, each with three terms. Equivalently, one can think of this as ${\pm 1}$ variables and ternary products. The objective is to maximize the fraction of satisfied equations.

Example 1 (Example of MAX-E3LIN instance)

\displaystyle \begin{aligned} x_1 + x_3 + x_4 &\equiv 1 \pmod 2 \\ x_1 + x_2 + x_4 &\equiv 0 \pmod 2 \\ x_1 + x_2 + x_5 &\equiv 1 \pmod 2 \\ x_1 + x_3 + x_5 &\equiv 1 \pmod 2 \end{aligned}

\displaystyle \begin{aligned} x_1 x_3 x_4 &= -1 \\ x_1 x_2 x_4 &= +1 \\ x_1 x_2 x_5 &= -1 \\ x_1 x_3 x_5 &= -1 \end{aligned}

A diligent reader can check that we may obtain ${\frac34}$ but not ${1}$.

Remark 2

We immediately notice that

• If there’s a solution with value ${1}$, we can find it easily with ${\mathbb F_2}$ linear algebra.
• It is always possible to get at least ${\frac{1}{2}}$ by selecting all-zero or all-one.

The theorem we will prove today is that these “obvious” observations are essentially the best ones possible! Our main result is that improving the above constants to 51% and 99%, say, is NP-hard.

Theorem 3 (Hardness of MAX-E3LIN)

The ${\frac{1}{2}+\varepsilon}$ vs. ${1-\delta}$ decision problem for MAX-E3LIN is NP-hard.

This means it is NP-hard to decide whether an MAX-E3LIN instance has value ${\le \frac{1}{2}+\varepsilon}$ or ${\ge 1-\delta}$ (given it is one or the other). A direct corollary of this is approximating MAX-SAT is also NP-hard.

Corollary 4

The ${\frac78+\varepsilon}$ vs. ${1-\delta}$ decision problem for MAX-SAT is NP-hard.

Remark 5

The constant ${\frac78}$ is optimal in light of a random assignment. In fact, one can replace ${1-\delta}$ with ${\delta}$, but we don’t do so here.

Proof: Given an equation ${a+b+c=1}$ in MAX-E3LIN, we consider four formulas ${a \lor \neg b \lor \neg c}$, ${\neg a \lor b \lor \neg c}$, ${a \lor \neg b \lor \neg c}$, ${a \lor b \lor c}$. Either three or four of them are satisfied, with four occurring exactly when ${a+b+c=0}$. One does a similar construction for ${a+b+c=1}$. $\Box$

The hardness of MAX-E3LIN is relevant to the PCP theorem: using MAX-E3LIN gadgets, Ha}stad was able to prove a very strong version of the PCP theorem, in which the verifier merely reads just three bits of a proof!

Let ${\varepsilon, \delta > 0}$. We have

$\displaystyle \mathbf{NP} \subseteq \mathbf{PCP}_{\frac{1}{2}+\varepsilon, 1-\delta}(3, O(\log n)).$

In other words, any ${L \in \mathbf{NP}}$ has a (non-adaptive) verifier with the following properties.

• The verifier uses ${O(\log n)}$ random bits, and queries just three (!) bits.
• The acceptance condition is either ${a+b+c=1}$ or ${a+b+c=0}$.
• If ${x \in L}$, then there is a proof ${\Pi}$ which is accepted with probability at least ${1-\delta}$.
• If ${x \notin L}$, then every proof is accepted with probability at most ${\frac{1}{2} + \varepsilon}$.

2. Label Cover

We will prove our main result by reducing from the LABEL-COVER. Recall LABEL-COVER is played as follows: we have a bipartite graph ${G = U \cup V}$, a set of keys ${K}$ for vertices of ${U}$ and a set of labels ${L}$ for ${V}$. For every edge ${e = \{u,v\}}$ there is a function ${\pi_e : L \rightarrow K}$ specifying a key ${k = \pi_e(\ell) \in K}$ for every label ${\ell \in L}$. The goal is to label the graph ${G}$ while maximizing the number of edges ${e}$ with compatible key-label pairs.

Approximating LABEL-COVER is NP-hard:

Theorem 7 (Hardness of LABEL-COVER)

The ${\eta}$ vs. ${1}$ decision problem for LABEL-COVER is NP-hard for every ${\eta > 0}$, given ${|K|}$ and ${|L|}$ are sufficiently large in ${\eta}$.

So for any ${\eta > 0}$, it is NP-hard to decide whether one can satisfy all edges or fewer than ${\eta}$ of them.

3. Setup

We are going to make a reduction of the following shape:

In words this means that

• “Completeness”: If the LABEL-COVER instance is completely satisfiable, then we get a solution of value ${\ge 1 - \delta}$ in the resulting MAX-E3LIN.
• “Soundness”: If the LABEL-COVER instance has value ${\le \eta}$, then we get a solution of value ${\le \frac{1}{2} + \varepsilon}$ in the resulting MAX-E3LIN.

Thus given an oracle for MAX-E3LIN decision, we can obtain ${\eta}$ vs. ${1}$ decision for LABEL-COVER, which we know is hard.

The setup for this is quite involved, using a huge number of variables. Just to agree on some conventions:

Definition 8 (“Long Code”)

A ${K}$-indexed binary string ${x = (x_k)_k}$ is a ${\pm 1}$ sequence indexed by ${K}$. We can think of it as an element of ${\{\pm 1\}^K}$. An ${L}$-binary string ${y = (y_\ell)_\ell}$ is defined similarly.

Now we initialize ${|U| \cdot 2^{|K|} + |V| \cdot 2^{|L|}}$ variables:

• At every vertex ${u \in U}$, we will create ${2^{|K|}}$ binary variables, one for every ${K}$-indexed binary string. It is better to collect these variables into a function

$\displaystyle f_u : \{\pm1\}^K \rightarrow \{\pm1\}.$

• Similarly, at every vertex ${v \in V}$, we will create ${2^{|L|}}$ binary variables, one for every ${L}$-indexed binary string, and collect these into a function

$\displaystyle g_v : \{\pm1\}^L \rightarrow \{\pm1\}.$

Picture:

Next we generate the equations. Here’s the motivation: we want to do this in such a way that given a satisfying labelling for LABEL-COVER, nearly all the MAX-E3LIN equations can be satisfied. One idea is as follows: for every edge ${e}$, letting ${\pi = \pi_e}$,

• Take a ${K}$-indexed binary string ${x = (x_k)_k}$ at random. Take an ${L}$-indexed binary string ${y = (y_\ell)_\ell}$ at random.
• Define the ${L}$-indexed binary ${z = (z_\ell)_\ell}$ string by ${z = \left( x_{\pi(\ell)} y_\ell \right)}$.
• Write down the equation ${f_u(x) g_v(y) g_v(z) = +1}$ for the MAX-E3LIN instance.

Thus, assuming we had a valid coloring of the graph, we could let ${f_u}$ and ${g_v}$ be the dictator functions for the colorings. In that case, ${f_u(x) = x_{\pi(\ell)}}$, ${g_v(y) = y_\ell}$, and ${g_v(z) = x_{\pi(\ell)} y_\ell}$, so the product is always ${+1}$.

Unfortunately, this has two fatal flaws:

1. This means a ${1}$ instance of LABEL-COVER gives a ${1}$ instance of MAX-E3LIN, but we need ${1-\delta}$ to have a hope of working.
2. Right now we could also just set all variables to be ${+1}$.

We fix this as follows, by using the following equations.

Definition 8 (Equations of reduction)

For every edge ${e}$, with ${\pi = \pi_e}$, we alter the construction and say

• Let ${x = (x_k)_k}$ be and ${y = (y_\ell)_\ell}$ be random as before.
• Let ${n = (n_\ell)_\ell}$ be a random ${L}$-indexed binary string, drawn from a ${\delta}$-biased distribution (${-1}$ with probability ${\delta}$). And now define ${z = (z_\ell)_\ell}$ by

$\displaystyle z_\ell = x_{\pi(\ell)} y_\ell n_\ell .$

The ${n_\ell}$ represents “noise” bits, which resolve the first problem by corrupting a bit of ${z}$ with probability ${\delta}$.

• Write down one of the following two equations with ${\frac{1}{2}}$ probability each:

\displaystyle \begin{aligned} f_u(x) g_v(y) g_v(z) &= +1 \\ f_u(x) g_v(y) g_v(-z) &= -1. \end{aligned}

This resolves the second issue.

This gives a set of ${O(|E|)}$ equations.

I claim this reduction works. So we need to prove the “completeness” and “soundness” claims above.

4. Proof of Completeness

Given a labeling of ${G}$ with value ${1}$, as described we simply let ${f_u}$ and ${g_v}$ be dictator functions corresponding to this valid labelling. Then as we’ve seen, we will pass ${1 - \delta}$ of the equations.

5. A Fourier Computation

Before proving soundness, we will first need to explicitly compute the probability an equation above is satisfied. Remember we generated an equation for ${e}$ based on random strings ${x}$, ${y}$, ${\lambda}$.

For ${T \subseteq L}$, we define

$\displaystyle \pi^{\text{odd}}_e(T) = \left\{ k \in K \mid \left\lvert \pi_e^{-1}(k) \cap T \right\rvert \text{ is odd} \right\}.$

Thus ${T}$ maps subsets of ${L}$ to subsets of ${K}$.

Remark 9

Note that ${|\pi^{\text{odd}}(T)| \le |T|}$ and that ${\pi^{\text{odd}}(T) \neq \varnothing}$ if ${|T|}$ is odd.

Lemma 10 (Edge Probability)

The probability that an equation generated for ${e = \{u,v\}}$ is true is

$\displaystyle \frac{1}{2} + \frac{1}{2} \sum_{\substack{T \subseteq L \\ |T| \text{ odd}}} (1-2\delta)^{|T|} \widehat g_v(T)^2 \widehat f_u(\pi^{\text{odd}}_e(T)).$

Proof: Omitted for now\dots $\Box$

6. Proof of Soundness

We will go in the reverse direction and show (constructively) that if there is MAX-E3LIN instance has a solution with value ${\ge\frac{1}{2}+2\varepsilon}$, then we can reconstruct a solution to LABEL-COVER with value ${\ge \eta}$. (The use of ${2\varepsilon}$ here will be clear in a moment). This process is called “decoding”.

The idea is as follows: if ${S}$ is a small set such that ${\widehat f_u(S)}$ is large, then we can pick a key from ${S}$ at random for ${f_u}$; compare this with the dictator functions where ${\widehat f_u(S) = 1}$ and ${|S| = 1}$. We want to do something similar with ${T}$.

Here are the concrete details. Let ${\Lambda = \frac{\log(1/\varepsilon)}{2\delta}}$ and ${\eta = \frac{\varepsilon^3}{\Lambda^2}}$ be constants (the actual values arise later).

Definition 11

We say that a nonempty set ${S \subseteq K}$ of keys is heavy for ${u}$ if

$\displaystyle \left\lvert S \right\rvert \le \Lambda \qquad\text{and}\qquad \widehat{f_u}(S) \ge \varepsilon^2.$

Note that there are at most ${\varepsilon^{-2}}$ heavy sets by Parseval.

Definition 12

We say that a nonempty set ${T \subseteq L}$ of labels is ${e}$-excellent for ${v}$ if

$\displaystyle \left\lvert T \right\rvert \le \Lambda \qquad\text{and}\qquad S = \pi^{\text{odd}}_e(T) \text{ is heavy.}$

In particular ${S \neq \varnothing}$ so at least one compatible key-label pair is in ${S \times T}$.

Notice that, unlike the case with ${S}$, the criteria for “good” in ${T}$ actually depends on the edge ${e}$ in question! This makes it easier to keys than to select labels. In order to pick labels, we will have to choose from a ${\widehat g_v^2}$ distribution.

Lemma 13 (At least ${\varepsilon}$ of ${T}$ are excellent)

For any edge ${e = \{u,v\}}$, at least ${\varepsilon}$ of the possible ${T}$ according to the distribution ${\widehat g_v^2}$ are ${e}$-excellent.

Proof: Applying an averaging argument to the inequality

$\displaystyle \sum_{\substack{T \subseteq L \\ |T| \text{ odd}}} (1-2\delta)^{|T|} \widehat g_v(T)^2 \left\lvert \widehat f_u(\pi^{\text{odd}}(T)) \right\rvert \ge 2\varepsilon$

shows there is at least ${\varepsilon}$ chance that ${|T|}$ is odd and satisfies

$\displaystyle (1-2\delta)^{|T|} \left\lvert \widehat f_u(S) \right\rvert \ge \varepsilon$

where ${S = \pi^{\text{odd}}_e(T)}$. In particular, ${(1-2\delta)^{|T|} \ge \varepsilon \iff |T| \le \Lambda}$. Finally by \Cref{rem:po}, we see ${S}$ is heavy. $\Box$

Now, use the following algorithm.

• For every vertex ${u \in U}$, take the union of all heavy sets, say

$\displaystyle \mathcal H = \bigcup_{S \text{ heavy}} S.$

Pick a random key from ${\mathcal H}$. Note that ${|\mathcal H| \le \Lambda\varepsilon^{-2}}$, since there are at most ${\varepsilon^{-2}}$ heavy sets (by Parseval) and each has at most ${\Lambda}$ elements.

• For every vertex ${v \in V}$, select a random set ${T}$ according to the distribution ${\widehat g_v(T)^2}$, and select a random element from ${T}$.

I claim that this works.

Fix an edge ${e}$. There is at least an ${\varepsilon}$ chance that ${T}$ is ${e}$-excellent. If it is, then there is at least one compatible pair in ${\mathcal H \times T}$. Hence we conclude probability of success is at least

$\displaystyle \varepsilon \cdot \frac{1}{\Lambda \varepsilon^{-2}} \cdot \frac{1}{\Lambda} = \frac{\varepsilon^3}{\Lambda^2} = \eta.$

(Addendum: it’s pointed out to me this isn’t quite right; the overall probability of the equation given by an edge ${e}$ is ${\ge \frac{1}{2}+\varepsilon}$, but this doesn’t imply it for every edge. Thus one likely needs to do another averaging argument.)

format: plain


text:
> "now you are talking again about sloshing, while the previous discussion was about electric circuits. "

The electric/hydrodynamic analogues can be deduced by comparing to the wave equation formulated in this paper by the ENSO researcher Allan Clarke [1]

[1]A. J. Clarke, S. Van Gorder, and G. Colantuono, [“Wind stress curl and ENSO discharge/recharge in the equatorial Pacific,”](http://yly-mac.gps.caltech.edu/AGU/AGU_2008/Zz_Others/Li_agu08/Clarke2007.pdf) Journal of physical oceanography, vol. 37, no. 4, pp. 1077–1091, 2007.

Look at his equations (4.1), (4.5), and (4.6) where $D$ (the 20°C isotherm depth anomaly) and $T$ (the sea surface temperature anomaly) act as hydrological mathematical analogues for the voltage/current & capacitance/inductance formulation of electric circuits.

$\frac{\partial D}{\partial t} = -\mu T$

$\frac{\partial T}{\partial t} = \nu D$

then substituting one into the other, he derives (4.6)

$T_{tt} + \omega^2 T = 0$

where the *tt* subscript notation is the second derivative with respect to time.

To finalize the analogy the resonant condition relates to the LC electrical resonance.

$\sqrt{\mu \nu} = \omega^2$

The unpredictability of sloshing is due to the fact that $\omega$ effectively changes cyclically as the forcing changes due to the massive weight of the fluid volume will effectively modify the factors $\nu$ and $\mu$ in some regular pattern.

This effect well known in the sloshing literature, and I am simply applying it to a larger volume than sloshing researchers such as Frandsen and Faltinsen apply it to, which is large fluid volumes held within sea-faring tankers. They are simply applying the math of hydrodynamics to an engineering problem, while I am extending it to understanding the dynamics of ocean sloshing.

I don't think that Clarke (or any other ENSO researcher) has put 2 and 2 together and thought to extend the wave equation to match the rather obvious sloshing dynamics that the hydrological engineers have been applying for several years now.

This is the breakthrough idea that ENSO research needs.

> "which gave me some frowns, as applying finite difference methods to nonlinear equations (and they talk about Bousinesq equations etc.) might not be appropriate. But as said I only glanced at the paper i.e. I even couldn't see in their not easy to read notation wether they actually apply that method. I just wanted to warn you, since I don't know how familiar you are with the discretization of nonlinear equations."

I have seen your concerns echoed by Boeing engineers that work fluid dynamics problems for flight simulators. I just don't buy it. The papers and books by Frandsen and Faltinsen go though the validation of the hydrodynamic formulation against the numerical results. Other researchers further confirmed what they have found. The validation is actually pretty simple. They run their hydrodynamics codes through a numerical solver and find that the standing wave patterns match closely to the Mathieu function. The Mathieu function is the transcendental solution to the Mathieu equation, which is well-documented and found for example in the [Mathematica library](http://mathworld.wolfram.com/MathieuFunction.html). This is in fact a perfect way to validate that your numerical integration schemes are solid -- no different than numerically solving the linear wave equation and finding that the result is a Sin or Cos.


text:
# Difference between revisions of "Chemical kinetics parameters"

## General notes

Spinach has a very general chemical kinetics module that can handle arbitrary reaction networks, the only restriction being that the corresponding differential equations must be linear and must have the following general form:

$\frac{d}{dt}\left( \begin{matrix} [\text{A}] \\ [\text{B}] \\ [\text{C}] \\ \vdots \\ \end{matrix} \right)=\mathbf{K}\left( \begin{matrix} [\text{A}] \\ [\text{B}] \\ [\text{C}] \\ \vdots \\ \end{matrix} \right)$

where $\mathbf{K}$ is the reaction rate matrix. For example:

$\begin{matrix} \text{A }\xrightarrow{{{k}_{1+}}}\text{ B }\underset{{{k}_{2-}}}{\overset{{{k}_{2+}}}{\longleftrightarrow}}\text{ C} \\ \frac{d}{dt}\left( \begin{matrix} \text{ }\!\![\!\!\text{ A }\!\!]\!\!\text{ } \\ \text{ }\!\![\!\!\text{ B }\!\!]\!\!\text{ } \\ \text{ }\!\![\!\!\text{ C }\!\!]\!\!\text{ } \\ \end{matrix} \right)=\left( \begin{matrix} -{{k}_{1+}} & 0 & 0 \\ {{k}_{1+}} & -{{k}_{2+}} & {{k}_{2-}} \\ 0 & {{k}_{2+}} & -{{k}_{2-}} \\ \end{matrix} \right)\left( \begin{matrix} \text{ }\!\![\!\!\text{ A }\!\!]\!\!\text{ } \\ \text{ }\!\![\!\!\text{ B }\!\!]\!\!\text{ } \\ \text{ }\!\![\!\!\text{ C }\!\!]\!\!\text{ } \\ \end{matrix} \right) \\ \end{matrix}$

Spinach expects you to supply this matrix and the initial concentrations of the molecules, as well as to say which spins in the spin system specification belong to which molecule. Spinach can also assist in determining the steady-state concentrations (see equilibrate.m) if you do not know them.

## Networks of chemical reactions

Your entire spin system must be specified multiple times, and then Spinach must be told which spins in the input stream belong to which reaction endpoint. For example, for a three-spin system where conformational exchange is happening between two configurations:

    % Isotopes
sys.isotopes={'1H','13C','15N','1H',13C','15N'};

% Chemical shifts
inter.zeeman.scalar={1.0, 20.0, 15.0, 1.5, 25.0, 16.0};

% Spins 1,2,3 are in the reactant; spins 4,5,6 are in the product
inter.chem.parts={[1 2 3],[4 5 6]};

% Kinetic rate matrix (Hz)
inter.chem.rates=[-0.1 0.2; 0.1 -0.2];

% Initial concentrations (arbitrary units)
inter.chem.concs=[1.0, 2.0]

In the general case, the the parameters, supplied to create.m at the spin system specification stage, must be:

Reaction kinetics parameters
Variable name Variable type Content
inter.chem.parts a cell array of vectors containing integers individual vectors in the cell array must contain the numbers of spins that belong to each of the molecules in the chemical reaction, for example {[1 2],[3 4]} indicates that spins 1 and 2 belong to the first molecule and spins 3 and 4 belong to the second molecule.
inter.chem.rates a matrix of real numbers chemical reaction rate matrix between the molecules identified in inter.chem.parts
inter.chem.concs a vector of non-negative real numbers initial concentrations of the molecules identified in inter.chem.parts

Note that all molecules must have the same number of spins, must have those spins specified in the same order, and must have the same basis set. Only the Liouville space formalism using the spherical tensor basis set is supported for this option.

## Spin state fluxes

There are rare cases when the magnetization is transferred through some indirect mechanism within a topologically fixed molecule, for example, a proton swap between two N-H groups of the same molecule. Because protons are fundamentally identical, this essentially amounts to swapping the spin state (together with all associated correlations to all external spins) between the two protons. In this case, the user should supply the matrix of magnetization flux rates between spins, for example:

    % Isotopes
sys.isotopes={'15N','1H','1H'};

% Chemical shift tensors
inter.zeeman.eigs{1}=[-50 -50 100];
inter.zeeman.euler{1}=[0.1 0.2 0.3];
inter.zeeman.eigs{2}=[-5 -5 10]+1;
inter.zeeman.euler{2}=[0.2 0.3 0.1];
inter.zeeman.eigs{3}=[-5 -5 10]+5;
inter.zeeman.euler{3}=[0.3 0.1 0.2];

% J-couplings
inter.coupling.scalar=cell(3,3);
inter.coupling.scalar{1,2}=50;

% Coordinates
inter.coordinates={[0.00 0.00 0.00];
[1.05 0.00 0.00];
[0.00 3.50 0.00]};

% Swapping the protons and their correlations
inter.chem.flux_rate=zeros(3,3);
inter.chem.flux_rate(2,3)=1000;
inter.chem.flux_rate(3,2)=1000;
inter.chem.flux_type='intramolecular';

In the general case, the the parameters, supplied to create.m at the spin system specification stage, must be:

Magnetisation flux parameters
Variable name Variable type Content
inter.chem.flux_rate nspins × nspins matrix of real numbers magnetization transport rates, in Hz
inter.chem.flux_type string: 'intermolecular', 'intramolecular' controls the fate of correlations with external spins, which are damped in the 'intermolecular' case and transported in the 'intramolecular' case.

The flux type parameter requires further explanation. When we swap a pair of spins in a molecule, their coherences with any observer spins should in general be preserved. This is what the 'intramolecular' option does. There are cases, however, when the exchange happens through some external medium, such as the solvent, or the end point of the jump is a different molecule. This would lead to the emergence of inter-molecular coherences between identical molecules – a situation that the density matrix formalism is ill-equipped to accommodate. Because such coherences are non-observable, and the spin is very unlikely to jump back to the exact same molecule that it had originally come from, the coherences in question are counted as lost. The corresponding contribution to the kinetics superoperator effectively causes relaxation. This is what happens when the 'intermolecular' option is specified.

This exotic process occurs in radical pairs involved in CIDNP, where the two-electron singlet state recombines (and forms diamagnetic products) faster than the two-electron triplet state. Because the rate of the singlet-triplet interconversion depends on the hyperfine couplings present, the result is the sorting of nuclei by orientation (some nuclear spin states accumulate in diamagnetic products, others are left behind in the unreacted radicals).

The kinetic modelling of the process is reviewed in the recent paper by Peter Hore and co-authors (http://dx.doi.org/10.1016/j.cplett.2011.03.082). The exponential model, the Haberkorn model and the Jones-Hore model are currently supported in Spinach. An example of the specification appears below:

    % Particles present
sys.isotopes ={'E','E','1H'};

% g-factors and chemical shifts
inter.zeeman.scalar={2.0023 2.0024 1.0};

% Hyperfine couplings
inter.coupling.scalar=cell(3,3);
inter.coupling.scalar{2,3}=1e7;

inter.chem.rp_theory='haberkorn';

% Electron identification
inter.chem.rp_electrons=[1 2];

% Singlet and triplet recombination rates
inter.chem.rp_rates=[1e7 0];

In the general case, the the parameters, supplied to create.m at the spin system specification stage, must be:

Magnetisation flux parameters
Variable name Variable type Content
inter.chem.rp_theory string: 'exponential', 'haberkorn', 'jones-hore' radical pair recombination theory
inter.chem.rp_electrons 1 x 2 vector of integers rlectron spins involved in the recombination reaction.
inter.chem.rp_rates 1 x 2 vector of reals singlet and triplet recombination rates in a radical pair, in Hz

The theory is only applicable to systems with exactly two unpaired electrons in Liouville space formalisms.

## Markov State Models

An MSM is essentially a multi-site chemical exchange model involving multiple configurations that have neen identified by clustering molecular dynamics simulations. To specify an MSM, do the following:

1. Get your molecular dynamics package to output the configurations as separate PDB files.
2. Generate the corresponding BMRB files with chemical shifts.
3. Import individual configurations using protein.m function.
4. Merge individual Spin_system_specification that protein.m returns into single large sys and inter structures.
5. Specify which spin belongs to which configuration as described in

Version 2.4, authors: Ilya Kuprov, Hannah Hogben, Peter Hore


text:
# What is the time complexity of the RC4 encryption & decryption algorithms?

I'm trying to figure out what the time complexity of RC4 encryption & decryption algorithms is, in big-O-notation.

-
This is very similar to Complexity of ECB and OFB; note that most stream ciphers like RC4 behave very much like a block cipher in OFB mode. Anyway, the short answer is, it's all $O(n)$. –  Ilmari Karonen May 26 '12 at 18:10

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit.

So:

 c = m ⊕ G(k)
m = c ⊕ G(k)

Where c is ciphertext, m is plaintext, G is the RNG and k is the key.

As such, all stream ciphers should be O(n) against the length of input data.

-
thank you very much !! How about for Block Cipher like AES? is it O(n) too? –  Kriss Wen May 23 '12 at 6:15
Most block ciphers will be O(n) against the number of blocks, yes. –  Polynomial May 23 '12 at 7:30
Keep in mind, though, that time complexity is practically meaningless as a measure of speed in this sense, because it tells you nothing about how fast the cipher is. If it always takes 10 milliseconds to encrypt a block in a cipher, it's O(n). If it always takes 10 minutes to encrypt a block in a cipher, it's still O(n). –  Polynomial May 23 '12 at 7:39

Any reversible cipher will need at least $\Omega(n)$ time (where $n$ is the size of the plaintext), since we need to touch each bit at least once.

A stream cipher (i.e. deterministic pseudo-random bit generator) does some fixed amount of work for each bit (or larger unit) of output (with maybe some initial preparation overhead), which is $O(n)$.

A block cipher needs some fixed (or at least, bounded) amount of work for each block.

All common bulk encryption block cipher modes of operation need just $O(n)$, too, since they execute the block cipher once (or another fixed amount) for each block of data, together with some fixed amount of work around these calls.

This shows that it is possible to do encryption in $O(n)$, thus I would never ever use a cipher for bulk encryption which takes longer than $O(n)$ ... and I don't think there are any serious proposals of such ones.

As Polynomial noted, the input size complexity doesn't tell anything about the actual speed of a cipher, as they are all in the same complexity class.

A more interesting use of complexity is when we have a family of algorithms with some modifiable security parameter $k$ (such as key size). Then we can look at the complexity of encrypting or decrypting (or various attacks on the cipher).

But still actual time and other resource usage when implementing the cipher on a computer (or other devices) for common choices of the security parameters is interesting, when comparing it to other competing algorithms.

-


text:
# Volume of distribution

The volume of distribution (VD) , also known as apparent volume of distribution, is a pharmacological term used to quantify the distribution of a medication between plasma and the rest of the body after oral or parenteral dosing. It is defined as the theoretical volume in which the total amount of drug would need to be uniformly distributed to produce the desired blood concentration of a drug.[1] [2]

Volume of distribution may be increased by renal failure (due to fluid retention) and liver failure (due to altered body fluid and plasma protein binding). Conversely it may be decreased in dehydration.

The initial volume of distribution describes blood concentrations prior to attaining the apparent volume of distribution and uses the same formula.

## Equations

The volume of distribution is given by the following equation:

${V_{D}} = \frac{\mathrm{total \ amount \ of \ drug \ in \ the \ body}}{\mathrm{drug \ blood \ plasma \ concentration}}$

Therefore the dose required to give a certain plasma concentration can be determined if the VD for that drug is known. The VD is not a physiologic value; it is more a reflection of how a drug will distribute throughout the body depending on several physicochemical properties, e.g. solubility, charge, size, etc.

The units for Volume of Distribution are typically reported in (ml or liter)/kg body weight. The fact that VD is a ratio of a theoretical volume to a fixed unit of body weight explains why the VD for children is typically higher than that for adults, even though children are smaller and weigh less. As body composition changes with age, VD decreases.

The VD may also be used to determine how readily a drug will displace into the body tissue compartments relative to the blood:

${V_{D}} = {V_{P}} + {V_{T}} \left(\frac{fu}{fu_{t}}\right)$

Where:

• VP = plasma volume
• VT = apparent tissue volume
• fu = fraction unbound in plasma
• fuT = fraction unbound in tissue

## Examples

Understanding volume of distribution

If you administer a dose D of a drug intravenously in one go (IV-bolus), you would naively expect it to have an immediate blood concentration C0 which directly corresponds to the amount of blood contained in the body Vblood. Mathematically this would be:

C0 = D / Vblood

But this is generally not what happens. Instead you observe that the drug has distributed out into some other volume (read organs/tissue). So probably the first question you want to ask is how much of it is no longer in the blood stream? The volume of distribution VD quantifies just that by specifying how big a volume you would need in order to observe the blood concentration actually measured.

A practical example for a simple case (mono-compartmental) would be to administer D=8 mg/kg to a human. A human has a blood volume of around Vblood = 0.08 l/kg [3]. This gives a C0 = 100 µg/ml if the drug stays in the blood stream only, and thus its volume of distribution is the same as Vblood that is VD = 0.08 l/kg. If the drug distributes into all body water the volume of distribution would increase to approximately VD = 0.57 l/kg [4]

If the drug readily diffuses into the body fat the volume of distribution may increase dramatically, an example is chloroquine which has a VD = 250-302 l/kg [5]

In the simple mono-compartmental case the volume of distribution is defined as: VD = D / C0, where the C0 in practice is an extrapolated concentration at time=0 from the first early plasma concentrations after an IV-bolus administration (generally taken around 5min - 30min after giving the drug).

Table of volume of distribution for drugs

 Drug VD Comments Warfarin 8L Reflects a high degree of plasma protein binding. Theophylline, Ethanol 30L Represents distribution in total body water. Chloroquine 15000L Shows highly lipophilic molecules which sequester into total body fat. NXY-059 8L Highly-charged hydrophilic molecule.

## Sample values and equations

Characteristic Description Example value Abbreviation(s) Formula
Dose Loading dose (LD), or steady state / maintenance dose (MD). 500 mg $\textstyle D$ design parameter
τ Dosing interval. 24 h $\textstyle \tau$ design parameter
Volume of distribution The apparent volume in which a drug is distributed immediately after it has been injected intravenously and equilibrated between plasma and the surrounding tissues. 6.0 L $\textstyle V_d$ $\textstyle = D / C_0$
Concentration Initial or steady-state concentration of drug in plasma. 83.3 µg/mL $\textstyle C_{0} \ or \ C_{ss}$ $\textstyle = D / V_d$
Biological half-life The time required for the concentration of the drug to reach half of its original value. 12 h $\textstyle t_{1/2}$ $\textstyle = ln (2) / k_{e}$
Elimination rate constant The rate at which drugs are removed from the body. 0.0578 h-1 $\textstyle k_e$ $\textstyle = ln (2) / t_{1/2} = CL / V_{d}$
Elimination rate Rate of infusion required to balance elimination. 50 mg/h $\textstyle k_{in}$ $\textstyle = C_{ss} \cdot CL$
Area under the curve The integral of the concentration-time curve (after a single dose or in steady state). 1320 µg/mL×h $\textstyle AUC_{0-\infty}$

$\textstyle AUC_{\tau,ss}$
$= \int_{0}^{\infty}C\, dt$
$= \int_{t}^{t+\tau}C\, dt$
Clearance The volume of plasma cleared of the drug per unit time. 0.38 L/h $\textstyle CL$ $\textstyle= V_{d} \cdot k_{e} = D/AUC$
Bioavailability The fraction of drug that is absorbed. 0.8 $\textstyle f$ $= \frac{AUC_{po}\cdot D_{iv}}{AUC_{iv}\cdot D_{po}}$
Cmax The peak plasma concentration of a drug after oral administration. 60.9 µg/mL $\textstyle C_{max}$ direct measurement
tmax Time to reach Cmax. 3.9 h $\textstyle t_{max}$ direct measurement
Cmin The lowest (trough) concentration that a drug reaches before the next dose is administered. 27.7 µg/mL $\textstyle C_{min,ss}$ direct measurement
Fluctuation Peak trough fluctuation within one dosing interval at steady state 41.8 % $\textstyle %PTF$ $\textstyle =100 \cdot \frac{(C_{max,ss} - C_{min,ss})}{C_{av,ss}}$
where
$\textstyle C_{av,ss}=\frac{AUC_{\tau,ss}}{\tau}$
edit

## References

1. ^ http://www.merckmanuals.com/professional/sec21/ch324/ch324d.html
2. ^
3. ^ Alberts, Bruce (2005). "Leukocyte functions and percentage breakdown". Molecular Biology of the Cell. NCBI Bookshelf. Retrieved 2007-04-14.
4. ^ Guyton, Arthur C. (1976). Textbook of Medical Physiology (5th ed.). Philadelphia: W.B. Saunders. p. 424. ISBN 0-7216-4393-0.
5. ^ Wetsteyn JC (1995). "The pharmacokinetics of three multiple dose regimens of chloroquine: implications for malaria chemoprophylaxis". Br J Clinical Pharmacology 39 (6): 696–9. PMID 7654492.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Volume de distribution — Pour les articles homonymes, voir Vd. Le volume de distribution, ou volume apparent de distribution, est un paramètre caractérisant la distribution (voir Pharmacocinétique de la substance active (dans un médicament) dans le corps humain. Son… …   Wikipédia en Français

• volume of distribution — a dilution method for determining the volume of fluids, e.g., plasma, in a body fluid compartment. A solute (e.g., inulin) is injected into the compartment and, after it is equally distributed, a sample is taken. The quantity of solute removed… …   Medical dictionary

• Initial volume of distribution — The initial volume of distribution is a pharmacological term used to quantify the distribution of a drug throughout the body relatively soon after oral or intravenous dosing of a drug and prior to the drug reaching a steady state equilibrium.… …   Wikipedia

• Table of volume of distribution for drugs — This is a table of volume of distribution (Vd) for various medication. For comparison, those with a Vd/kg body weight of less than 0.2 are mainly distributed in blood plasma, 0.2 0.7 mostly in the extracellular fluid and those with more than 0.7… …   Wikipedia

• Distribution (pharmacology) — Distribution in pharmacology is a branch of pharmacokinetics which describes the reversible transfer of drug from one location to another within the body. The distribution of a drug between tissues is dependent on permeability between tissues… …   Wikipedia

• Distribution De Temps De Séjour — L’expression de distribution de temps de séjour s utilise en génie des procédés. La distribution de temps de séjour est un modèle qui permet de caractériser l hydrodynamique d un réacteur chimique et de déterminer quel modèle de réacteur définit… …   Wikipédia en Français

• DISTRIBUTION (économie) — Pour la Chambre de commerce internationale, la distribution est «le stade qui suit celui de la production des biens à partir du moment où ils sont commercialisés jusqu’à leur prise en possession par le consommateur ou l’utilisateur final. Elle… …   Encyclopédie Universelle

• Distribution (Commerce) — Distribution (management) Le management de la distribution est l organisation de la mise à disposition d un produit ou d un service à un intermédiaire ou un consommateur final. Cette organisation sera différente si ce management est réalisé par… …   Wikipédia en Français

• Distribution (management) — Le management de la distribution est l organisation de la mise à disposition d un produit ou d un service à un intermédiaire ou un consommateur final. Cette organisation sera différente si ce management est réalisé par une entreprise dont l… …   Wikipédia en Français

• Volume rendering — is a technique used to display a 2D projection of a 3D discretely sampled data set.A typical 3D data set is a group of 2D slice images acquired by a CT or MRI scanner.Usually these are acquired in a regular pattern (e.g., one slice every… …   Wikipedia


text:
# How to separate Even and odd part (in-phase bit streams I and quadrature-bit streams Q) of the signal?

I am working on communication system in simulink and wondering, how can i separate the Even and odd part of the signal.

In my Transmitter block, I have :

$$\boxed{\text{Binary Data signal}}{\longrightarrow}\boxed{\text{Serial to parallel}}^{\nearrow\boxed{\text{Even Part}}{\longrightarrow}\boxed{\text{Multiply PN code}}{\longrightarrow}\text{signal}}_{\searrow\boxed{\text{Odd Part}}{\longrightarrow}\boxed{\text{Multiply PN code}}{\longrightarrow}\text{signal}}$$ Not sure how to separate those two part from signal ? Also can i use below equations for channels I and Q. $$I(t) = \sqrt{\frac{2E_s}{T} \cos(\omega t)\cos(45+n)}$$

$$Q(t) = \sqrt{\frac{2E_s}{T} \sin(\omega t) \sin(45+n)}$$

The OP is mis-understanding how this QPSK signaling scheme operates.

There is a stream of input bits $$b_0, b_1, b_2, b_3, \ldots,$$ that is coming serially at the rate of one bit every $$T$$ seconds, so $$b_0$$ during $$[0,T)$$, $$b_1$$ during $$[T,2T)$$, and more generally, $$b_n$$ during $$[nT, (n+1)T)$$.. So, there is a clock signal at $$\frac 1T$$ Hz at the input.

The first thing that happens is the serial-to-parallel conversion where the serial bit stream gets converted into a stream of dibits (two bits in parallel), one bit on each of two individual wires and each bit lasting for $$2T$$ seconds (that is, the dibit lasts for $$2T$$ seconds. Thus, we have $$(b_0, b_1) \to \left[\begin{matrix}b_0\\b_1\end{matrix}\right], \quad (b_2, b_3) \to \left[\begin{matrix}b_2\\b_3\end{matrix}\right], \cdots \cdots (b_{2n}, b_{2n+1}) \to \left[\begin{matrix}b_{2n}\\b_{2n+1}\end{matrix}\right], \cdots$$ So immediately we need to understand that

• The output of the serial-to-parallel converter is clocked at with a clock at $$\frac{1}{2T}$$ Hz, and this clock is synchronized with the input clock of the serial to parallel converter,
• There is a delay of $$2T$$ seconds in that $$\left[\begin{matrix}b_0\\b_1\end{matrix}\right]$$ is the output of the serial-to-parallel converter during $$[2T,4T)$$, $$\left[\begin{matrix}b_2\\b_3\end{matrix}\right]$$ is the output during $$[4T,6T)$$, and so on,
• The "even bits" have been sorted into appearing on the upper wire and the "odd bits" on the lower of the two wires, just as is envisioned in the OP's diagram. These are the Inphase and Quadrature branches of the transmitter.

The dibit enters into the direct-sequence modulator which says multiplication but this is if the bits ($$0$$ or $$1$$) have been converted into real numbers $$+1$$ and $$-1$$ respectively, and ditto the PN sequence. The logical operation with $$0$$s and $$1$$ is the XOR operation: the bit $$b$$ lasting $$2T$$ seconds is replaced by a serial stream of $$N$$ bits $$(b\oplus \text{PN}_0, b\oplus \text{PN}_1, \cdots, b\oplus \text{PN}_{N-1})$$ which last for a total of $$2T$$ seconds. Thus the PN sequence generators (usually different ones in the I and Q branches) are clocked at $$\frac{N}{2T}$$ Hz, and this clock is also synchronous with all the other clocks.

Everything is digital up to this point. To get the actual transmitted signal, the $$0$$s and $$1$$s are mapped to $$\pm 1$$, each rectangular pulse (of duration $$2T/N$$ seconds in the direct-sequence QPSK system) is replaced by the desired baseband pulse shape (e.g. root raised cosine) to get the complex baseband representation $$I(t)+jQ(t)$$ of the QPSK signal. The actual RF signals in the I and Q branches of the transmitter are $$I(t)\cos(2\pi f_c t)$$ and $$-Q(t)\sin(2\pi f_c t)$$ where $$f_c \gg \frac{1}{2NT}$$ is the RF carrier frequency. Thus the actual RF QPSK signal is of the form $$s(t) = I(t)\cos(2\pi f_c t)-Q(t)\sin(2\pi f_c t) = \text{Re}\big((I(t)+jQ(t))\exp(j2\pi f_ct)\big)$$ and results from modulating a (spread) dibit onto an RF carrier. Dibits consist of two bits; all Americans know that make two bits make a quarter, which explains why they think that the Q in QPSK stands for quaternary instead of quadrature or quadriphase.....


text:
## 13. In a division sum, the divisor is 12 times the quotient and 5 times the remainder. If the remainder is 48, then the dividend i

Question

13. In a division sum, the divisor is 12 times the
quotient and 5 times the remainder. If the
remainder is 48, then the dividend is

in progress 0
2 days 2021-10-12T12:17:36+00:00 1 Answer 0 views 0

Step-by-step explanation:

let the divisor be d, quotient be q and remainder be rthen quotient=12q=dand remainder=5r=dNow, 5r=dput r=48=>5×48=d=>240=dnow, 12q=240=>q=20now, …  More

IParthThakre9965Expert

let the divisor be d, quotient be q and remainder be r

then quotient=12q=d

and remainder=5r=d

Now, 5r=d

put r=48

=>5×48=d

=>240=d

now, 12q=240

=>q=20

now,

dividend=divisor × quotient + remainder

=>240*20+48

=>4848

Therefore, 4848 is the dividend!

I HOPE IT HELPS YOU


text:
# Christmas Streak 15/88: This Is A Bit Repulsive

Geometry Level 3

Tom has a set of particles that repel each other with a force of $$F(r)$$ whose strength is proportional to $$\frac{1}{r^2},$$ where $$r$$ is the distance of separation between any pair of particles.

If Tom puts 8 of these particles into a rigid, frictionless sphere and allows them to come to rest, they'll align to the vertices of a certain $$n$$-faced polyhedron.

What is $$n?$$

For example, if Tom puts 4 of the particles into the sphere, they'll come to rest at the vertices of a regular tetrahedron, as shown.

×


text:
4. Please circle the following molecule(s) that would be classified as aromatic:NH

Question:

4. Please circle the following molecule(s) that would be classified as aromatic: NH

Similar Solved Questions

Spring Manufacturing Company makes two components identified as C12 and D57. Selected budgetary data for 2019...
Spring Manufacturing Company makes two components identified as C12 and D57. Selected budgetary data for 2019 follow: Finished Components c12 D57 Requirements for each finished component: RM 1 RM 2 10 pounds 0 2 pounds 2 hours 8 pounds 4 pounds 1 pound 3 hours RM 3 Direct labor Product information: ...
Which one of the following sets of parametric equations does not correspond to the rectangular equation y = 41 - 22x(t) =ty(t) = 4 - 2 r(t) 4+4v6) =1 [+ r(t) 2 J(t) = 2t ~(t) = Zty(t) = 8t -4
Which one of the following sets of parametric equations does not correspond to the rectangular equation y = 41 - 22 x(t) =ty(t) = 4 - 2 r(t) 4+4v6) =1 [+ r(t) 2 J(t) = 2t ~(t) = Zty(t) = 8t -4...
Examples of Eurobonds and foreign bonds.
Examples of Eurobonds and foreign bonds....
A certain plane flying with the wind travels 540 km in 2 hours
A certain plane flying with the wind travels 540 km in 2 hours. Later, flying against the same wind, the plane travels 690 km in 3 hours. Find the speed of the plane in still air and the speed of the boat. A boat takes 3 hours to go 24 km upstream. It can go 36 km downstream in the same time. Find t...
Explain Lydia Hall's nursing theory. how did her theory promote the delivery of competent nursing care?...
Explain Lydia Hall's nursing theory. how did her theory promote the delivery of competent nursing care? (please type, if you are not sure don't give guessing answer and don't give just the definition) :)...
Suppose and B are two independent events_ Given; P(A) 0.3, and P(AUB) 0.2 Determine the probability of event B. Comment if they are mutually exclusive. [4 marks] (6) What is a hypothesis test? Briefly explain: [2 marks]
Suppose and B are two independent events_ Given; P(A) 0.3, and P(AUB) 0.2 Determine the probability of event B. Comment if they are mutually exclusive. [4 marks] (6) What is a hypothesis test? Briefly explain: [2 marks]...
2_ [10] Solve the following equation for (2 x 2) matrix X:2('1)(9) 'x+r 3Jx(9-(4)
2_ [10] Solve the following equation for (2 x 2) matrix X: 2 ('1)(9) 'x+r 3Jx(9-(4)...
Which of the following statements regarding the Isthmus of Panama are CORRECT? (Select ALL that are correct} Oa Is responsible for the many pairs of geminate marine specles found between the western Atlantic Ocean and eastern Pacific Ocean In that region today: Facilitated the phenomenon known Js the Great American Interchange. Played an important role in limiting the dispersal organisms that could (ly: Now serves a5 barrier t0 many marine arganisms but J5 = Bateway for many terrestrial Organism
Which of the following statements regarding the Isthmus of Panama are CORRECT? (Select ALL that are correct} Oa Is responsible for the many pairs of geminate marine specles found between the western Atlantic Ocean and eastern Pacific Ocean In that region today: Facilitated the phenomenon known Js th...
Calculate the energy required to raise the temperature of 5.00 mol of aluminum by 20.0PC. The specific heat of aluminum is 0.903 Jlg %C3.6 ]90.3]244*1033.3]97 ]
Calculate the energy required to raise the temperature of 5.00 mol of aluminum by 20.0PC. The specific heat of aluminum is 0.903 Jlg %C 3.6 ] 90.3] 244*103 3.3] 97 ]...
Identify and explain what are the four financial statements. 1.Income Statement 2. Statement of Retained Earnings...
Identify and explain what are the four financial statements. 1.Income Statement 2. Statement of Retained Earnings 3. Balance Sheet 4. Statement of Cash Flow What are the types of accounts included on each statement. Identify the relationship between each statement. Cite your sources (APA)....
(3 points) Find the derivative of f(x) 6berf'(x)
(3 points) Find the derivative of f(x) 6ber f'(x)...
Before you begin this chapter, check your skill level by trying the exercises in the puzzle. If you have trouble with any of these problems, come back to the puzzle as you work through the chapter, and fill in the answers that gave you trouble. $3^{3} \cdot 1000$
Before you begin this chapter, check your skill level by trying the exercises in the puzzle. If you have trouble with any of these problems, come back to the puzzle as you work through the chapter, and fill in the answers that gave you trouble. $3^{3} \cdot 1000$...
Part A Figure < 1 of 1 If the beam is subjected to a bending moment...
Part A Figure < 1 of 1 If the beam is subjected to a bending moment of M = 2 kN.m, determine the bending stress developed at point A. (Figure 1) Express your answer to three significant figures and include the appropriate units. Enter negative value in the case of compression and positive in the ...
Refer to Eigure 15.1 which lists the prices of various Microsoft options Use the data in the figure to calculate the payoff and the proft/loss for investments in each of the following July...
Refer to Eigure 15.1 which lists the prices of various Microsoft options Use the data in the figure to calculate the payoff and the proft/loss for investments in each of the following July 2017 expiration options on a single share, assuming that the stock price on the expiration date is S76 (Leave n...
Can someone help me with this problem please Find the area under the standard normal curve...
can someone help me with this problem please Find the area under the standard normal curve between z = -1.8 and 2 = -0.23. Round your answer to four decimal places, if necessary. Answer 4 Points Keypad If you would like to look up the value in a table, select the table you want to view, then eith...
Problem 2 (25 pts.) A steel column has a total unbraced height of 20 ft and...
Problem 2 (25 pts.) A steel column has a total unbraced height of 20 ft and carries an axial LRFD load of 500 kips. The column ends are fixed. Select an economical HSS 8x8 for this column....
Two blocks of masses $M_{1}$ and $M_{2}$ are connected with a string passing over a pulley as shown in Fig. $7.355$. The block $M_{1}$ lies on a horizontal surface. The coefficient of friction between the block $M_{1}$ and the horizontal surface is $mu$. The system accelerates. What additional mass $m$ should be placed on the block $M_{1}$ so that the system does not accelerate?a. $frac{M_{2}-M_{1}}{mu}$b. $frac{M_{2}}{mu}-M_{1}$c. $M_{2}-frac{M_{1}}{mu}$d. $left(M_{2}-M_{1}ight) mu$
Two blocks of masses $M_{1}$ and $M_{2}$ are connected with a string passing over a pulley as shown in Fig. $7.355$. The block $M_{1}$ lies on a horizontal surface. The coefficient of friction between the block $M_{1}$ and the horizontal surface is $mu$. The system accelerates. What additional mass ...
23. Let the random variable X have the probability density function 3x} if xe[o,2] f(x) = otherwise Find E(X ) 213 3/4 85 125 14/5 None of these24. Let the random variable X have the probability density functione-I1O_ if x20 f(x)={10 othervise Find E(X) 1/101/100 100None of these
23. Let the random variable X have the probability density function 3x} if xe[o,2] f(x) = otherwise Find E(X ) 213 3/4 85 125 14/5 None of these 24. Let the random variable X have the probability density function e-I1O_ if x20 f(x)={10 othervise Find E(X) 1/10 1/100 100 None of these...
What is the pH of a solution that consists of $0.20 \mathrm{M}$ ammonia, $\mathrm{NH}_{3},$ and $0.20 \mathrm{M}$ ammonium chloride, $\mathrm{NH}_{4} \mathrm{Cl} ?$
What is the pH of a solution that consists of $0.20 \mathrm{M}$ ammonia, $\mathrm{NH}_{3},$ and $0.20 \mathrm{M}$ ammonium chloride, $\mathrm{NH}_{4} \mathrm{Cl} ?$...
Description Zac Ltd and Tess Lid entered into a joint operation known as Trouble Ltd to...
Description Zac Ltd and Tess Lid entered into a joint operation known as Trouble Ltd to collect and recycle empty water bottles from government departments on 1 January 2020. The joint operation agreement states that Zac Ltd and Tess Ltd will share output contributions and costs equally and that Zac...
Paul was discussing the market for cocoa beans with his friend John. Paul said, "Ever since...
Paul was discussing the market for cocoa beans with his friend John. Paul said, "Ever since Venezuela announced that its cocoa harvest was its lowest ever in fifteen years, the price of cocoa beans has been rising and rising and people are buying more and more. I think the demand for cocoa beans...
A small machine shop manufactures drill bits used in the petroleum industry. The manager estimates that...
A small machine shop manufactures drill bits used in the petroleum industry. The manager estimates that the total daily cost (in dollars) of producing X bits is ... CIX) 1,000 25X - 0.13x2 Find the average cost of producing 10 units. (Round to the nearest 2 decimal places, if needed)...
10) Please provide the requested information below: (A-D 3 points each:)Rh(pPkascl Qulkinsonts calatyshMeOPCY3PCYaPa(Pensla KCO,Pa(pensha KCO,Please give me Ihe Oxidation State (0.5.) and number = valence electrons (%e) for each metal complex below: points each) HyN PCY3 Pi_ci oc Fe HyN PC} Gadum common chemolherpeubc)0&:04:04:
10) Please provide the requested information below: (A-D 3 points each:) Rh(pPkascl Qulkinsonts calatysh MeO PCY3 PCYa Pa(Pensla KCO, Pa(pensha KCO, Please give me Ihe Oxidation State (0.5.) and number = valence electrons (%e) for each metal complex below: points each) HyN PCY3 Pi_ci oc Fe HyN PC} G...
According to the Income Tax Act, which of the following items is the starting point for...
According to the Income Tax Act, which of the following items is the starting point for computing net business income for tax purposes? Choose the correct answer. A. Sales revenue less cost of goods sold B. Net income for a business computed using generally accepted accounting principl...
An angry store owner named Alexandra strikes a customer named Fahim with a shovel. Which of...
An angry store owner named Alexandra strikes a customer named Fahim with a shovel. Which of the following is most likely to occur? Value: 2 marks. Select one: a. The Crown initiates a civil proceeding against Alexandra b. Fahim initiates proceedings in an appellate court c. Fahim initiates proceedin...
Need help on this 1. D. Belle created a new business and invested $6,000 cash.$7600...
need help on this 1. D. Belle created a new business and invested $6,000 cash.$7600 of equipment, and $12,000 in web servers in exchange for common stock 2. The company paid$4,800 cash in advance for prepaid Insurance coverage. 3. The company purchased \$900 of supplies on account. 4. The compan...
7. (8 pts) Rewrite the following integral using Cylindrical coordinates_ Do NOT evaluate_ 9-312_3y? ( 21 3y dz dy dx Vs-T2 Il+y2_11
7. (8 pts) Rewrite the following integral using Cylindrical coordinates_ Do NOT evaluate_ 9-312_3y? ( 21 3y dz dy dx Vs-T2 Il+y2_11...
Consider the following V = M2z' s= {[8 %] [: %] [--}} Complete the following statements_The elements of set 6Select---linearly independent:The set 6 haselements and dim(Mz2)Therefore, the set 6Select-basis for V.
Consider the following V = M2z' s= {[8 %] [: %] [--}} Complete the following statements_ The elements of set 6 Select--- linearly independent: The set 6 has elements and dim(Mz2) Therefore, the set 6 Select- basis for V....
Consumer BchaviorMarketing 8102 scceseful usuIk Ananat high brand-name und logo recognition consumers_ exaple Coi- fmx Cola produets are Aaulable 98"" of all people in the world and may have the [ogo recognition of an} compuny colnrare un higrest = 4"cloping product wculd like t estimate the proportion of who recognize the inux penguin logo, Of the 952 Fcupi Fadcxely ~elected consumers surveyed [32 could identify the ProJuct associated with the penguin distribution of the sample
Consumer Bchavior Marketing 8102 scceseful usuIk Ananat high brand-name und logo recognition consumers_ exaple Coi- fmx Cola produets are Aaulable 98"" of all people in the world and may have the [ogo recognition of an} compuny colnrare un higrest = 4"cloping product wculd like t est...
Help pleaseee In the lac operon, positive control occurs through the presence of the CAMP-CAP complex....
help pleaseee In the lac operon, positive control occurs through the presence of the CAMP-CAP complex. This complex is not available in the presence of glucose. this would mean that: When lactose is present, the lac operon will be activated only if glucose is absent When lactose is absent, the lac ...
The size of certain insect population is given by P() = S00e 01 , where t is measured in days At what lirne will the population equal 3000?It will take days for Ihe populalion equal 3000 . (Round to one decimal place as needed )
The size of certain insect population is given by P() = S00e 01 , where t is measured in days At what lirne will the population equal 3000? It will take days for Ihe populalion equal 3000 . (Round to one decimal place as needed )...


text:
• Most awarded test prep in the world
Now free for 30 days

Available with Beat the GMAT members only code

• Free Practice Test & Review
How would you score if you took the GMAT

Available with Beat the GMAT members only code

• Magoosh
Study with Magoosh GMAT prep

Available with Beat the GMAT members only code

• Free Veritas GMAT Class
Experience Lesson 1 Live Free

Available with Beat the GMAT members only code

• 1 Hour Free
BEAT THE GMAT EXCLUSIVE

Available with Beat the GMAT members only code

• Free Trial & Practice Exam
BEAT THE GMAT EXCLUSIVE

Available with Beat the GMAT members only code

• Award-winning private GMAT tutoring

### GMAT/MBA Expert

EconomistGMATTutor GMAT Instructor
Joined
04 Oct 2017
Posted:
545 messages
Followed by:
10 members
180
Tue Oct 10, 2017 5:27 am
Hello GMATinsight and Regor.

I would like to give you a more detailed solution.

We have 6 horses and we can have the following cases:

- Horse A finishes 1st: here, we have to organize 5 horses in 5 places, the number of ways to do that is A*5*4*3*2*1=5!=120.

- Horse A finishes 2nd: First, we have to pick the horse for the first place but we can not select horses B or C. So, we have 3 options for the first place (D, E, F) and the number of ways to select a horse for the first place is 3. Then we have to organize 4 horses in the last 4 places. The total number of ways in this case is 3*A*4*3*2*1=72.

- Horse A finishes 3rd: as in the case before, we have to pick 2 horses for the first 2 places but we can not select horses B or C. So, we have 3 options again and we can organize this 2 horses in 3*2=6 different ways. Now we have to organize the last 3 horses in the last 3 places. The total number of ways in this case is 3*2*A*3*2*1=36.

- Horse A finishes 4th: Now, we have to pick 3 horses for the first 3 places but we can not select horses B or C, the number of ways to organize this 3 horses is 3*2*1=6. Finally, we have to organize 2 horses (B and C) in the last 2 places. The total number of ways in this case is 3*2*1*A*2*1=12.

You should noticed that A can not finish in the 5th place or in the 6th place.

In conclusion, the total number of ways this race can end is 120+72+36+12=240.

So, the correct answer is C.

_________________
GMAT Prep From The Economist
We offer 70+ point score improvement money back guarantee.
Our average student improves 98 points.

Free 7-Day Test Prep with Economist GMAT Tutor - Receive free access to the top-rated GMAT prep course including a 1-on-1 strategy session, 2 full-length tests, and 5 ask-a-tutor messages. Get started now.

### Top Member

regor60 Master | Next Rank: 500 Posts
Joined
15 Oct 2009
Posted:
236 messages
27
Thu Sep 28, 2017 7:11 am
A finishes 1st: 5 options for B x 4 options C x 3 x 2 options for D,E,F = 120
2nd: 4....3...." = 72
3rd: 3.....2..." = 36
4th: 2........." = 12

Total 240 C

### Best Conversation Starters

1 lheiannie07 108 topics
2 Roland2rule 63 topics
3 ardz24 63 topics
4 LUANDATO 50 topics
5 AAPL 42 topics
See More Top Beat The GMAT Members...

### Most Active Experts

1 GMATGuruNY

The Princeton Review Teacher

152 posts
2 Jeff@TargetTestPrep

Target Test Prep

106 posts
3 Rich.C@EMPOWERgma...

EMPOWERgmat

104 posts
4 Scott@TargetTestPrep

Target Test Prep

96 posts
5 Max@Math Revolution

Math Revolution

87 posts
See More Top Beat The GMAT Experts


text:
# Math Help - Derivitive Question

1. ## Derivitive Question

Hi all. I am getting into the chain rule in my Calculus with Matrices business course. I've come across a problem, our system is all online, and i cannt figure it out. They examples they provided were pretty simple and staight forward, but i cannot put htis one together. I'm sure its really easy, but i'd appreciate it if someone would explain

If f(x)= $\frac{1}{X^2 +1}$
then f '(x) is what? The system tell me the answer is $\frac{-2X}{(X^2+1)^2}$

I cannot figure out even where to start on this problem nor which derivative rule to use. I'm probably overcomplicating it, but if any one would be willing to help i'd greatly appreciate it!

2. Well, since it's a fraction you could consider the quotient rule, but my advice is to rewrite it as $(x^2+1)^{-1}$ and then just apply the exponent/power rule together with the chain rule. Give it a shot

3. hey thanks. sorry about the edits, i was playing with the javascript math thing. really neat.

i'll give it a show

4. Also, I hate that I forget those basic rules like 1 over a number is the same thing as the denominator of the number to the -1 power. is there a website that i can refesh all that stuff at?

Thanks again for the help

5. the "+ 1" is driving me crazy. I dont know waht to do with it. OUr examples didnt tell us what to do if there was any addition or subtraction in the problems w/ the chain rule

6. The derivative is lineair, so the derivative of a sum is equal to the sum of the derivatives.
The derivative of a constant is 0, so (x²+1)' = (x²)' + (1)' where ' means derivative, what does that give?

7. Hi:

The chain rule is intended to facilitate differentiation of composite functions. In general, if f(g(x)) is the composition of function f with function g, then f '(x) = f '(g) * g '(x). For instance, consider y = e^sin(x). Here y=e^x is composed with u=sin(x). To simplify the thinking, we can write y = e^sin(x) as y = e^u where u=sin(x). So, dy/dx = dy/du * du/dx. Recalling the derivatives of e^x and sin(x) as e^x and cos(x) respectively, it follows that:

dy/dx = dy/du * du/dx = e^u * cos(x) = e^sin(x) * cos(x)

In the case at hand, f(x) = (x^2+1)^-1 can be inturpreted as u^-1 where
u = x^2+1. Hence f '(x) = -1* u^-2 * du/dx = -[x^2+1]^-2 * 2x or,
f '(x) = -2x / [x^2+1]^2.

Regards,

Rich B.


text:
Determine whether $\sum_{n=1}^\infty \frac{\sin^2 n}{n^2}$ converges or diverges

I've been given this interesting problem but I'm not too sure how to go about it.

My first thought was to find the limit of $\frac{\sin^2 n}{n^2}$ by using the squeeze theorem and then applying the divergence test to determine if the sum converges or diverges.

After finding the limit of the expression, I realized that I cannot apply the divergence test since the limit is $0$, and this doesn't tell me anything.

How else could I go about solving this problem?

• Did you try the comparison test? – user99914 Sep 29 '15 at 4:00
• The summation does in fact converge to $\frac{1}{2}(\pi-1)$ if that helps – Brevan Ellefsen Sep 29 '15 at 4:02
• Okay, I have to know how you calculated that – William Stagner Sep 29 '15 at 4:02
• @WilliamStagner I used Mathematica. Wolfram Alpha has the partial sums, but it is messy. I'm sure there is a more elegant proof that could be constructed, I just threw that out there as an interesting observance. I am now curious as to whether there is a simple way to prove this... I'll look into it for a bit – Brevan Ellefsen Sep 29 '15 at 4:06
• The sum $\sum_{n\in \mathbb{Z}} \sin^2(n)/n^2 = \pi$ can be evaluated easily using Parseval's identity. The result stated by @BrevanEllefsen then follows because $\sin^2 n/n^2$ is even under $n\mapsto -n$. – Fabian Sep 29 '15 at 4:48

Using the natural bound for $\sin$ gets easier: We have $$\frac{\sin^{2}n}{n^{2}} \leq \frac{1}{n^{2}}$$ for all $n \geq 1$; the series $\sum_{n\geq 1}\frac{1}{n^{2}}$ converges; so by the comparison test the desired series converges.
• @Nitin: Thanks; that is correct; I was being sloppy... But note that it is the square of $\sin$ takes place. – Megadeth Sep 29 '15 at 4:18
Maybe it's interesting to see a way to find the sum of the series. Using the well-known trigonometric identity $$\sin^{2}\left(x\right)=\frac{1}{2}\left(1-\cos\left(2x\right)\right)$$ we have $$\sum_{n\geq1}\frac{\sin^{2}\left(n\right)}{n^{2}}=\frac{1}{2}\left(\sum_{n\geq1}\frac{1}{n^{2}}-\sum_{n\geq1}\frac{\cos\left(2n\right)}{n^{2}}\right)$$ and note, using the representation $$\cos\left(2n\right)=\frac{e^{2in}+e^{-2in}}{2}$$ that the last series is $$\sum_{n\geq1}\frac{\cos\left(2n\right)}{n^{2}}=\frac{1}{2}\left(\textrm{Li}_{2}\left(e^{2i}\right)+\textrm{Li}_{2}\left(e^{-2i}\right)\right)$$ which is, using the dilogarithm identity, $$\textrm{Li}_{2}\left(z\right)+\textrm{Li}_{2}\left(z^{-1}\right)=-\frac{\pi^{2}}{6}-\frac{1}{2}\log^{2}\left(-z\right)$$ hence $$\sum_{n\geq1}\frac{\sin^{2}\left(n\right)}{n^{2}}=\frac{1}{2}\left(\frac{\pi^{2}}{6}+\frac{\pi^{2}}{12}+\frac{1}{4}\log^{2}\left(-e^{2i}\right)\right)=\frac{1}{2}\left(\pi-1\right).$$


text:
Department of Mathematics

Inside this content area:

Ranking and total ordering on sets of fuzzy numbers

Zhenyuan Wang

Description

Using the knowledge on relations and fuzzy sets, give a theoretical description of rankings and total orderings on sets consisting of fuzzy numbers. A view point of reference systems may be adopted. Some criteria for the goodness of ranking and total orderings are introduced. Sufficient examples are cited to illustrate the results.

References

[1] D. Dubois and H. Prade, Ranking fuzzy numbers in the setting of possibility theory, Information Sciences 30, 183-224, 1983.
[2] W. Wang and Z. Wang, Total ordering defined on the set of all fuzzy numbers, submitted to international journal of Fuzzy Sets and Systems.
[3] Y. J. Wang and H. S. Lee, The revised method of ranking fuzzy numbers with an area between the centroid point and original point, Computers and Mathematics with Applications 55, 2033-2042, 2008.
[4] Z. Wang, R. Yang, and K. S. Leung, Nonlinear integrals and Their Applications in Data Mining, World Scientific, Singapore, 2010.
[5] Z. Wang and L. Zhang-Westman, The cardinality of the set of all fuzzy numbers, Proc. IFSA2013. 1045-1049.
[6] L. Zhang-Westman and Z. Wang, Ranking fuzzy numbers by their left and right wingspans, IFSA2013, 1039-1044.

MATH 8370

Requirements

Give the theoretical definitions of rankings and total orderings and discuss the relation between them to clean up the confusion in literature. Develop the criteria for the goodness of rankings and total ordering defined on various sets of fuzzy numbers. Some examples should be used to illustrate these results. A research paper on this topic should be completed and be submitted to some international academic conference or journal in time.


text:
# Non-continuous GpuMat after cv::cuda::transpose

Opencv3.0x64 Cuda6.5 Windows7x64

I have a continuous cv::cuda::GpuMat of homogeneous points organized in col major format. IE:

X1, X2, X3 .....
Y1, Y2, Y3 .....
1,  1,  1  .....

I am trying to transpose this and manipulate it into this format:

X1
Y1
1
X2
Y2
1
X3
Y3
1

To do this, I should be able to transpose the matrix, reshape it then transpose it again. Unfortunately when I do this I seem to run into a bug with cv::cuda::transpose. After transposing the first matrix, I should have a "diff" matrix like this:

X1, Y1, 1,
X2, Y2, 1,
...........

With floating point values, this should give a step size of 12 bytes and be continuous. Unfortunately the resultant matrix has a step size of 512 bytes and is non-continuous. Because of this, I cannot reshape the matrix.

Is this a bug with cv::cuda::transpose? I've tried the following:

cv::cuda::transpose(diff,diff);
diff = diff.reshape(1,1);
and
cv::cuda::transpose(diff,diff);
diff = diff.clone().reshape(1,1);
and
cv::cuda::transpose(diff,diff);
diff = diff.colRange(0,3).clone();
diff = diff.reshape(1,1);

No matter what, reshape throws the exception:

error: (-13) The matrix is not continuous, thus its number of rows can not be changed in function cv::cuda::GpuMat::reshape"

I've downloaded it and the downloaded copy is correct with a step size of 12. Is this some kind of alignment requirement in cuda? How can I reshape the matrix to what I need without downloading it to the CPU?

edit retag close merge delete


text:
Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR16-007 | 23rd January 2016 20:43

#### Property Testing, PCP, andJuntas

Revision #1
Authors: Guy Kindler
Accepted on: 23rd January 2016 20:43
Keywords:

Abstract:

This is a PhD Thesis, originally published in 2003, and put here now for accessibility, not novelty.

The first part of this thesis strengthens the low-error PCP
characterization of NP, coming closer to the upper limit of the
conjecture of BGLR. This result has been surpassed -- see the paper
"Polynomially Low Error PCPs with polyloglog n Queries via Modular
Composition" with Irit Dinur and Prahladh Harsha.

In the second part we show that a boolean function over
$n$ variables can be tested for the property of depending on only
$k$ of them, using a number of queries that depends only on $k$
and the approximation parameter $\epsilon$. After the thesis was
published, almost optimal parameters were obtained in the paper
"Testing Juntas Nearly Optimally" by E. Blais.

In the third part of this thesis we show that any boolean function
$f\colon\{0,1\}^n\to\{-1,1\}$ whose weight on Fourier-Walsh
products of size larger than $k$ is bounded by
$(\epsilon/k)^{(\ell+1)/\ell}$, where $\ell$ is any fixed positive
integer, is $O(\epsilon)$-close to a junta whose size is independent of
$n$. We also show that for small values of $\epsilon$, if the
weight of a boolean function $f$ on Fourier-Walsh products of size
larger than $k$ is $\epsilon$, then $f$ is $\epsilon(1+o(1))$-close to
a junta, whose size depends only on $k$. This is a generalization of
the result in~\cite{FKN}, who proved this for $k=1$, and only with
respect to the uniform measure. The first part of this result was
surpassed even before it was published by a paper named "On the
distribution of the Fourier spectrum of Boolean functions" by J.
Bourgain. A much simpler proof with improved parameters can be
found in a paper named "Gaussian noise sensitivity and Fourier tails"
with Ryan O`Donnell.

### Paper:

TR16-007 | 23rd January 2016 06:43

#### Property Testing, PCP, andJuntas

TR16-007
Authors: Guy Kindler
Publication: 23rd January 2016 14:08
Keywords:

Abstract:

The first part of this thesis strengthens the low-error PCP
characterization of NP, coming closer to the upper limit of the
conjecture of~\cite{BGLR}.

In the second part we show that a boolean function over
$n$ variables can be tested for the property of depending on only
$\size$ of them, using a number of queries that depends only on $\size$
and the approximation parameter $\err$.

In the third part of this thesis we show that any boolean function
$\f\colon\{0,1\}^n\to\{-1,1\}$ whose weight on Fourier-Walsh
products of size larger than $k$ is bounded by
$(\epsilon/k)^{(\ell+1)/\ell}$, where $\ell$ is any fixed positive
integer, is $O(\epsilon)$-close to a junta whose size is independent of
$n$. We also show that for small values of $\epsilon$, if the
weight of a boolean function $\f$ on Fourier-Walsh products of size
larger than $k$ is $\epsilon$, then $\f$ is $\epsilon(1+o(1))$-close to
a junta, whose size depends only on $k$. This is a generalization of
the result in~\cite{FKN}, who proved this for $k=1$, and only with
respect to the uniform measure.

ISSN 1433-8092 | Imprint