Recent content by jetoso

Thank you, I think this works.

Homework Statement We want to make an open box with squared base. Let x be the dimension of one side of the base and y the height of the box. We pay a cost of $1.00 /cm^2 for the base and $0.50/cm^2 for each side. The box must have a volume V = 6400 cm^3. Determine the dimensions x and y...

Thanks

Hello, I am trying to prove the following about equipotence: Let A and B be nonempty sets. We say that A is equipotent with B if there is a bijection between A and B. Then the following hold: (i) A is equipotent with itself. (ii) If A is equipotent with B, then B is equipotent with A. (iii)...

I want to build a binary matrix (with 1 and 0 entries) with all possible combinations, say for example if n is the number of entries of one row of the matrix, then 2^n is the total number of different entries in the matrix. For instance, for n=3, 2^n = 8, so we would have the following matrix...

Nevermind I think I solved this problem. Let x2 >= x1, and take y2 >= f(x1) = y'. Then, from the definition of f, we have: g(x1,f(x1)) - f(x1,y2) <= 0. Since g is superadditive is satisfies: g(x2,y2) + g(x1,f(x1)) >= g(x2,f(x1)) + g(x1,y2) From the first inequality above we get...

Homework Statement Show that a superadditive function has the following property: For any superadditive function g on XxY (cartesian product): f(x) = min { y' : y' = argmin g(x,y) } is nonincreasing in x. Homework Equations if g(x,y) is a superadditive on XxY, x in X, y in Y, x1 >=...

Thank you Thank you so much.

Homework Statement Show that the sum of two superadditive (supermodular) functions is superadditive. Homework Equations Let X and Y be partially ordered sets and g(x,y) a real-valued function on XxY. g is supermodular (superadditive) if for x1>=x2 in X and y1>=y2 in Y, g(x1,y1) +...

I have a question. Is the class of problems NP-Complete more difficult to solve than the class of problems NP-Hard? I mean, NP-Complete problems are in NP, and also are NP-Hard, but not all NP-Hard problems are in NP... How to tell which one is more difficult to solve?

I got it Well, I think I did not pay too much attention to this problem, it is very straight forward by the way, look: 2n^3 + 5n^2 + 8n + 3 = (2n + 1) (n^2 + 2n + 3) Thus, since the numerator is n^2 + 2n + 3, then it follows that: (n^2 + 2n + 3)/(2n + 1) (n^2 + 2n + 3) = 1/(2n + 1)...

Answer Say for n^2 + 2n + 3 we can write it as (n+1)^2 + 2, so we have that (n+1)(n+1) + 2 = n^2 + 2n + 3

I have a really bad time thinking on this: Factorize: (n^2 + 2n +3 ) / (2n^3 + 5n^2 + 8n +3) such that we end up with 1/(2n +1). I might be forgetting how to complete the square or the cube or something but I can not find a way to reduce it. Any advice?

It is well known that there is a dynamic programming recursion that solves the subset-sum problem in O(nt), where t is the target. Thus, if t is given in unary, then the running time must be bounded in polynomial-time of the size of the input. So, in principle the way in which the target is...

Is it possible to show that the SUBSET-SUM problem can be solved in polynomial time if the target t is given in unary? We know that the subset sum problem consist on finding a subset S' of numbers from a set S such that its sum equals t. If t is unary, say if t=3 then t=111, how can we...