## Top new questions this week:

### Why rectangle packing is NP-hard but maybe not in NP?

Recently I studied a MIT open course. In lecture2, it is stated that Rectangle Packing is NP-hard. I can understand this because the problem can be reduced to 3-partition problem But I don't know why ...

np-hard np decision-problem
 asked by Jxb Score of 8
 answered by Yuval Filmus Score of 16

Are there other advantages to linked lists over arrays other than constant time removals of the first element?

 asked by Austin Conlon Score of 5
 answered by Surprised Seagull Score of 17

### Name and complexity of this problem on bipartite graphs

Let $G=(U, V, E)$ be a biparite graph, with $U$ and $V$ being the two sets of nodes. I am trying to find the smallest set of nodes $\hat{V} \subseteq V$ such that, for every node $u \in U$, $\hat{V}_u$...

graphs np-hard bipartite-graph
 asked by Luigi Procopio Score of 4
 answered by Narek Bojikian Score of 2

### If $L$ is regular then so is $\{y \mid \exists x \, xyx \in L\}$

For a language $\mathcal{L}$ over an alphabet $\Sigma$, define $$\mathcal{SW(L)} := \{ y ∈ Σ^∗ \mid \exists x \in Σ^* \text{ such that } xyx \in \mathcal{L}\}$$ How can I prove that if $\mathcal{L}$ ...

regular-languages automata finite-automata
 asked by Shubhang Gupta Score of 4
 answered by Yuval Filmus Score of 4

Given the algorithm MYSTERY-ALG(n >= 0) 1 if n < 3 then 2 return 1 3 else 4 return MYSTERY-ALG(n/2) + MYSTERY-ALG((n/2) + 1) I defined a recurrence $... complexity-theory asymptotics runtime-analysis recurrence-relation  asked by Mampac Score of 3  answered by John L. Score of 4 ### Why can't$QBF$be reduced to$SAT$Let$QBF_k$be the problem of determining the satisfiability of a formula of the form$Φ = Q_1x_1Q_2x_2 . . . Q_kx_k φ(x_1, . . . , x_n)$. where each$Q_i$is one of the quantifiers$∀$or$∃$. So,$Φ$... reductions satisfiability  asked by SVMteamsTool Score of 3  answered by Steven Score of 6 ### Amortized analysis on a dynamic table that grows its size by$\sqrt{size} $The following problem is based on the section about dynamic table as part of the discussion about amortized analysis in CLRS Problem: We are given a dynamic table$T$that supports INSERT operation, ... algorithms algorithm-analysis amortized-analysis dynamic-array  asked by hazelnut_116 Score of 3  answered by John L. Score of 2 ## Greatest hits from previous weeks: ### What is the difference between object detection, semantic segmentation and localization? I've read those words in quite a lot of publications and I would like to have some nice definitions for those terms which make it clear what the difference between object detection vs semantic ... terminology computer-vision  asked by Martin Thoma Score of 31  answered by e3oroush Score of 19 ### Regular Expression for even-odd language of string I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over$\Sigma = \{a,b\}$, which is the set of strings with even numbers of$b$'s and odd number of$a$'... automata regular-expressions  asked by Khurram Ali Score of 4  answered by Ran G. Score of 8 ### What is a safe programming language? Safe programming languages (PL) are gaining popularity. I wonder what is the formal definition of safe PL. For example, C is not safe, but Java is safe. I suspect that the property “safe” should be ... programming-languages  asked by beroal Score of 61  answered by Davislor Score of 25 ### What is the definition of P, NP, NP-complete and NP-hard? I'm in a course about computing and complexity, and am unable to understand what these terms mean. All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea ... complexity-theory terminology complexity-classes p-vs-np reference-question  asked by Mirrana Score of 314  answered by Kaveh Score of 444 ### How to prove that a language is not regular? We learned about the class of regular languages$\mathrm{REG}$. It is characterised by any one concept among regular expressions, finite automata and left-linear grammars, so it is easy to show that a ... formal-languages regular-languages proof-techniques reference-question  asked by Raphael Score of 92  answered by Romuald Score of 71 ### How to prove that a language is not context-free? We learned about the class of context-free languages$\mathrm{CFL}$. It is characterised by both context-free grammars and pushdown automata so it is easy to show that a given language is context-free.... formal-languages context-free proof-techniques reference-question  asked by Raphael Score of 96  answered by jmad Score of 73 ### Which machine learning algorithms can be used for time series forecasts? Currently I am playing around with time series forecasts (specifically for Forex). I have seen some scientific papers about echo state networks which are applied to Forex forecast. Are there other ... reference-request machine-learning artificial-intelligence  asked by Maecky Score of 28  answered by rphv Score of 28 ## Can you answer these questions? ### A Single Row GUI Layout Algorithm I need a layout algorithm and use it in the GUI, but I can't use existing GUI toolkits at the moment, so I would like to find a layout algorithm. I only need to do a single row layout, and here is the ... algorithms graphics user-interface  asked by skiars Score of 1 ### Running time of 01-Knapsack-like with negative weight/values, absolute value weight constraint, and volume constraint? Background In the classic formulation of the knapsack problem with both weight and volume constraints, we are given a collection of$n$items where item$i$has weight$w_i\in\mathbb{N}$, volume$u_i\...

complexity-theory dynamic-programming knapsack-problems
 asked by Rando5 Score of 1

### Sum in counting satisfying assignments

Is there a polynomial-time algorithm that computes the sum of two boolean formulas, such that, (#SUM(F,G) = #F + #G), the output satisfying assignments equals the sum of the satisfying assignments of ...

algorithms complexity-theory satisfiability counting
 asked by Arnau M. Score of 1
 answered by Yuval Filmus Score of 0
You're receiving this message because you subscribed to the Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy

Stack Overflow, 110 William Street, 28th floor, New York, NY 10038

 <3