• Breaking News

    Sunday, November 29, 2020

    Home Unlabelled P=NP Problem Computer Science

    P=NP Problem Computer Science

    November 29, 2020

    P=NP Problem Computer Science

    P=NP Problem

    Posted: 29 Nov 2020 12:15 AM PST

    Ok so I have a rather specific question about the P=NP problem. If a single problem was shown to be unsolvable in polynomial time, but verifiable in polynomial time, would that prove that P does not equal NP?

    submitted by /u/slick-sharky
    [link] [comments]

    Understanding Backtracking by solving the N-Queens Problem And Knight's tour

    Posted: 28 Nov 2020 05:51 AM PST

    Recently I have been working on algorithms that I should have really learned in my Algorithms class. For this week and did backtracking, which is one of the fundamental algorithms of problem solving and AI.

    To practice I solved 2 problems. The n-queens and knight's tour.

    Here is the video where I go over the solution if you'd like to take a look at it: https://youtu.be/CQ3nDMcchdA

    Here is the code if you want to skip the video and go straight to it:
    https://github.com/challengingLuck/youtube/tree/master/backtracking

    Let me know what you think! All feedback is appreciated!

    submitted by /u/challenging-luck
    [link] [comments]

    in read-write locks, why do we need read locks?

    Posted: 29 Nov 2020 03:31 AM PST

    in read-write locks, why do we need read locks since processes can read a file at the same time? Would only a write lock suffice? Thanks.

    submitted by /u/timlee126
    [link] [comments]

    [Discussion/Topic of Interest] How would you prove this decision problem is in P, WITHOUT proving Goldbach Conjecture?

    Posted: 28 Nov 2020 09:48 PM PST

    Decision Problem: Given an input positive even-integer N, decide if it is the sum of two primes.

    Fact: The prime-gap grows logarithmically; even in the bit-length of N. This means a while loop can find primes < N that sum up to N.

    Example Algorithm

    ​

    https://preview.redd.it/fe8rytzvb4261.png?width=1197&format=png&auto=webp&s=2367632df4a603f7a8f49745ef70d8067c482088

    Because of the prime gap growing so slow; this algorithm runs in polynomial time in log(N).

    • If Goldbach Conjecture is true; it is in P.
    • Now, how would you prove it is in P. Without proving Goldbach's Conjecture?
    submitted by /u/Hope1995x
    [link] [comments]

    Are we really like 10th century blacksmiths?

    Posted: 28 Nov 2020 06:45 PM PST

    Hamha! (means Hello!)

    That's a weird way to start a message on Reddit, isn't it? It's an obscure reference to an old GBA game I once played and loved. Because starting a reddit post always gives me the "how do start this thing in a normal way..." kind of feeling, I decided to go the other direction for once.

    Now on to asking the real question here. I was browsing some old posts from a while ago and someone made the following comment:

    Computer scientists are like 10th century blacksmiths: we know what works, but we don't know why, and this prevents us from radically improving our craft.

    Since then, some time has passed and we've gotten a bit smarter. But the question remains, how far do you think we really are currently in the advancement of our field? Are we truly the gods some people make us out to be or indeed the equavalent to scruffy 10th century blacksmiths who can hit a piece of iron with a hammer and call it science?

    submitted by /u/OrdanOccluded
    [link] [comments]

    How do you efficiently find all maximal trees in an undirected connected graph?

    Posted: 28 Nov 2020 04:04 PM PST

    Ideas for Research in Combinatorial Optimization

    Posted: 28 Nov 2020 11:46 AM PST

    Hello, world! I will be finishing my computer science bachelor by the end of march 2021. I've already decided to pursue a master's degree right after I graduate. However, I don't really know what will my research topic be and this is making me really anxious, since the master program demand a ten-page essay of what my research is going to be about (along with a schedule).

    I am really interested in combinatorial optimization and everything involving it, such as graph & computation theory, soft computing, AI, operations research, metaheuristics, etc. My undergraduate thesis consisted in the development of a metaheuristic approach for the DARP (Dial-a-Ride Problem), which is a NP-hard problem that can be seen as a "generalized" TSP. I kinda enjoyed working on it, however it was very exhausting, since my advisors did not give a shit about it and I was on my very own. Thus I don't want to continue researching this specific topic (the DARP).

    My question is: what are some of the hot topics in these area(s) that could lead into research opportunities? I accept any suggestion in which I can put my mind in some papers. I know this may lead into many different kinds of answers, but anything would be definitely appreciated. Thank you.

    Ps: I thought about posting in r/csMajors but I think this question in much more related to CompSci than academia/career issues.

    submitted by /u/afellowboi
    [link] [comments]

    You Can Now Learn for FREE: 9 Courses by Google about Artificial Intelligence, Machine Learning and Data Science

    Posted: 28 Nov 2020 06:44 AM PST
    Read more
    at

    No comments:

    Post a Comment