Does your first programming language correlate to the career you are in?: Survey for Adults who know at least one programming language Computer Science

---

Does your first programming language correlate to the career you are in?: Survey for Adults who know at least one programming language Posted: 02 Jun 2018 06:07 PM PDT submitted by /u/Brymax21 [link] [comments]

Is this a sub-exponential solution to an NP-hard problem? Posted: 02 Jun 2018 08:57 PM PDT My purpose is to /attempt/ to show a sub-exponential solution to an NP-hard problem. The clique problem is, given a graph and positive integer k, determine if there exists clique with k vertices. (I believe I read somewhere earlier today it's NP-hard.) Suppose graph G has n vertices. There are (n choose k) sets of vertices with k vertices in each set. (n choose k) is maximized when k = n/2. The number of sets of vertices to check is maximized when k = n/2. In the worst case there are (n choose n/2) sets of vertices to check. (n choose n/2) = n! / [(n - n/2)! * (n/2)!] = n! / [(n/2)! * (n/2)!] = n! / [(n/2)!]2 If we replace x! with xx we get: nn / [(n/2)n/2]2 Using an online graphing calculator that function looks like it's identical to 2x. I will assume it is. https://ibb.co/eVDaoJ https://ibb.co/dCHeFy I'm told that nn grows faster than n!. Therefore we have: 2n = nn / [(n/2)n/2]2 > n! / [(n/2)!]2 At this point I haven't included checking the edges. That can be done in n2. I will assume multiplying by this term is still sub-exponential. So then we have n! * n2 / [(n/2)!]2 < 2n Does this mean there's a sub-exponential algorithm to an NP-hard problem? Or (very likely) did I make a mistake in my logic somewhere? submitted by /u/jaredmathis [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States