If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________

If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________ Correct Answer NP-complete

If the partial order has at most one minimal element, or it has at most one maximal element, then to test whether a partial order with multiple sources and sinks can be drawn as a crossing-free Hasse diagram or not it’s time complexity is NP-complete.
Bissoy MCQ

Related Questions

If u (x, y, z, t) = f(x + iβy - vt) + g(x - iβy - vt), where f and g are arbitrary and twice differentiable functions, is a solution of the wave equation $$\frac{{\partial {u^2}}}{{\partial {x^2}}} = \frac{{{\partial ^2}u}}{{\partial {y^2}}} = \frac{1}{{{c^2}}}\frac{{{\partial ^2}u}}{{\partial {t^2}}}$$     then β is
If a partial order is drawn as a Hasse diagram in which no two edges cross, its covering graph is called ______
On a P-V diagram of an ideal gas, suppose a reversible adiabatic line intersects a reversible isothermal line at point A. Then at a point A, the slope of the reversible adiabatic line $${\left( {\frac{{\partial {\text{P}}}}{{\partial {\text{V}}}}} \right)_{\text{S}}}$$  and the slope of the reversible isothermal line $${\left( {\frac{{\partial {\text{P}}}}{{\partial {\text{V}}}}} \right)_{\text{T}}}$$  are related as (where, $${\text{y}} = \frac{{{{\text{C}}_{\text{p}}}}}{{{{\text{C}}_{\text{v}}}}}$$  )
Are these statements about the minimal processing true? Statement 1: Appearance of the minimal processed product almost remains same. Statement 2: Shelf life of the minimal processed product is longer than conventional process.
Let $${\text{f}}\left( {{\text{x, y}}} \right) = \frac{{{\text{a}}{{\text{x}}^2} + {\text{b}}{{\text{y}}^2}}}{{{\text{xy}}}},$$     where a and b are constants. If $$\frac{{\partial {\text{f}}}}{{\partial {\text{x}}}} = \frac{{\partial {\text{f}}}}{{\partial {\text{y}}}}$$   at x = 1 and y = 2, then the relation between a and b is
The highest pressure gas of a mixture has partial pressure p, the partial pressure of other gases decreases by factor of 2n-1, the partial pressure of second gases decreases by a factor of 2, partial pressure of third gas increases by 4, and so on, if the total pressure of gas mixture is 31p/16, how many gases are present in the mixture?
The equation relating E, P, V and T which is true for all substanes under all conditions is given by $${\left( {\frac{{\partial {\text{E}}}}{{\partial {\text{V}}}}} \right)_{\text{T}}} = {\text{T}} \cdot {\left( {\frac{{\partial {\text{P}}}}{{\partial {\text{T}}}}} \right)_{\text{H}}} - {\text{P}}{\text{.}}$$      This equation is called the
Maxwell equation $${\left( {\frac{{\partial P}}{{\partial T}}} \right)_V} = {\left( {\frac{{\partial S}}{{\partial V}}} \right)_T}$$     is produced from which of the following equation
The solution of initial value problem; $$\frac{{\partial {\text{u}}}}{{\partial {\text{x}}}} = 2\frac{{\partial {\text{u}}}}{{\partial {\text{t}}}} + {\text{u,}}$$   where u(x, 0) = 6e-3x is
Which of the following statements about partial pressure are correct? Statement 1: The partial pressure of each gas in a mixture is not proportional to its mole fraction.. Statement 2: The partial pressure of each gas is the product of the total pressure and the mole fraction of that gas.