All Questions

11,629 questions
Filter by
Sorted by
Tagged with
64 views

A Simpler Solution for a special case of the Set Cover problem

We decomposed a simple polygon into many small regions. Then we estimated a visibility polygon of a point by a subset of the small regions. Now I need the minimum set of visibility polygons that can ...
61 views

How do we evalute the difference between a predicted value $\hat{v}$ and the true nash equlibrium value $v$

Consider a bimatrix game problem with matrix $A$ and $B$. The definition of the value $v = [v_1, v_2]$ of the Nash equilibrium $(x, y)$ are as follows, $$v_1 = x^TAy,$$ $$v_2 = x^TBy.$$ The situation ...
99 views

Can finite difference methods approximate the space/time complexity of given programs?

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page ...
210 views

Is this a novel technique for determining whether or not two rotated rectangles collide?

I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm: Rotate both rectangles by the negative rotation ...
143 views

I think I may have discovered a new algorithm for a common problem. Now what?

I was trying to solve a common problem the other week and upon checking Stackoverflow there was a solution, but it just seemed like there should be a better way to do it. I thought about it for a ...
241 views

Does Horn SAT (Horn formula in CNF) have an integral polytope?

In some ways, my question is related to this: Is the matching polytope integral? Matching and Horn-SAT are both polynomial time solvable.. So I wonder if there is a Horn polytope, similar to the ...
107 views

92 views

104 views

54 views

Number of composite factors as a function of the number of bits of an integer

Is there a standard formula to calculate the number of composite factors using the number of bits of an integer?
45 views

Using bin-packing algorithms to approximate maximum-makespan

Bin-packing (BP) and maximum-makespan (MM) are dual problems. In both problems, the input can be defined as a set $S$ of positive integers, and the output is a partition of $S$. In BP, there is a ...
5k views

Can theoretical computer science be applied in social sciences?

I'm very new to this field - technically not in it but want to be. I'm very early in my academic career (sophomore at a community college) but decided that I want to add a math major along with my ...
136 views

Is QMA known to contain Co-NP?

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
170 views

A variant of two-counter machine

I would like to show that the halting problem for some variant of two counter machine (Minsky machine) is undecidable: instead of "if c=0 goto i else goto j", there are "if c>d goto ...
168 views

Lexicographic Boolean satisfiability

Maximal Satisfying Assignment (Lexicographic Boolean satisfiability / LexMaxSAT), the problem of finding the lexicographically maximum x_1, . . . , x_n ∈ {0, 1}^n that satisfies Boolean formula φ, or ...
34 views

Bin Packing And Preemptive Multi-Core Scheduling

I am trying to solve a preemptive multi-core scheduling problem, where the input is the tasks. The number of cores M can be decided after seeing the input tasks. I ...
98 views

165 views

$\lambda$-definability and structure preserved by homomorphisms

I imagine there are some standard results that bear on this, but I'm having trouble finding a proof or refutation of it. Some prelimary definitions. A Henkin structure $A = (A^\cdot, ⟦\cdot⟧_A)$ for ...
The following result is adapted from Anthony and Bartlett, 1999 (Theorem 4.9). Theorem There exist positive constants $m_0 \le 400$, $c_1 \le 8$, $c_2 \le 41$, $c_3 \ge 1/576$ such that, if \$(\Omega,\...